Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: In this paper, the authors introduce a black box adversarial attack based on estimating the sign of the gradient. To estimate this more efficiently than the gradient itself, the authors exploit the fact that directional derivatives can be estimated using finite differences using only two function evaluations, and use a simple flip/revert procedure to estimate a number of sign bits simultaneously. This sign bit gradient vector is then used in place of the true gradient in an FGSM-like procedure. The central arguments are that (1) estimating the sign bits alone is sufficient to produce adversarial examples, and (2) this can be done quickly enough in practice to yield an efficient procedure.

Overall, I feel that this paper makes a decent contribution to blackbox adversarial generation in settings where confidence scores are available. In particular, many algorithms in this area are often quite complicated and involve machinery like genetic programming. Recent work has begun to demonstrate that significantly simpler routines can not only generate adversarial images, but can do so with significantly fewer queries than their more complicated counterparts. 

In particular, two of the methods compared to (NES, Bandits-TD) are state of the art or nearly state of the art, and seem to be significantly outperformed in most regimes considered -- at a glance it appears this approach may outperform other recent work that isn't compared to, such as the method of Guo et al., 2019. The inclusion of results on the public blackbox attack challenges is also welcome.

Could the authors comment on the apparent degradation of performance on L2 performance as the image dimensionality increases? Is this simply an artifact of the fact that the ||x||_{2} <= sqrt(n) ||x||_{\infty} bound directly scales with the input dimensionality? It would be interesting to verify this shortcoming by determining whether applying recent techniques for dimensionality reduction and approximating signed gradients in the subspace alters the relative performance of methods in the L2 perturbation constraint experiments.
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: Summary:
This paper proposes a black-box adversarial sample generation algorithm, which proceeds by learning the signs of the gradient using an adaptive query scheme, which the authors call _SignHunter_. The authors begin by deriving an upper bound on the query complexity for _SignHunter_. Next, the authors empirically compare the performance of _SignHunter_ 
with existing sign-based optimization schemes in the literature, and demonstrate the advantages of _SignHunter_. 


Main Comments: 

- Theoretical analysis of the Adaptive Scheme: The authors emphasize the adaptive nature of the proposed scheme as one of the contributions. However, this claim is not justified theoretically:  it would be interesting if the benefits of adaptivity could be quantified in terms of improved worst-case query complexity etc. as compared to any non-adaptive scheme. The query complexity of 2^{\log(n)+1} given in Theorem 1 is not very informative, since a lower complexity (n) is achieved by a simple open-loop  scheme which serially queries each coordinate (i.e., the first query is coordinate 1, the second query is coordinate 2, and so on). 

-  Comparison with Hazan el. al (2018): A closely related work in optimizing real-valued functions with domain \{-1,1\}^n is Hazan et. al published in ICLR 2018, which assumes that the black-box function is sparse or compressible in the Fourier domain, and employs compressed sensing techniques to get fast convergence rates in the optimization error. Since that paper considers a very similar optimization problem and proposes a scheme with provable convergence guarantees,  I think it is important that the authors compare,  either theoretically or empirically,  the performance of their proposed scheme with Harmonica (the algorithm of Hazan et al (2018)) to justify the benefits their proposed scheme. 

- Parameter Free Algorithm: The statement of Theorem 1 contains the following hypothesis: "the directional derivative is well approximated by the finite difference (Eq. 1)". This condition must be clarified, because it seems to contradict the claim made by the authors later in the last line of Page 5 that _SignHunter_ is "parameter-free" as they set \delta= \epsilon. The condition in the statement of Theorem 1 will not necessarily be satisfied for any \delta, and admissible values of \delta must depend on the properties of the function. Informally, I think that the condition will only be satisfied for \delta "small enough", and one way to make precise the meaning of "small enough" is in terms of the Lipschitz constant of the neural network. However, in that case, I am not sure that the algorithm would remain parameter-free.  I think the authors should make the assumption in Theorem 1 precise and derive suitable sufficient conditions on \delta under which the assumption is satisfied.

References:
1. Hazan, Elad, Adam Klivans, and Yang Yuan. "Hyperparameter optimization: A spectral approach." ICLR (2018).

review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: I'm satisfied with the response. I'll keep my original rating towards acceptance.

----------------------------

This paper proposes a black-box adversarial attack method to improve query efficiency and attack success rate. Instead of estimating the gradient of a black-box model, the proposed method estimates the sign of the gradient, which is an easier task. The SignHunter algorithm is proposed to estimate the sign of the gradient by a divide-and-conquer search. And adversarial examples are generated based on the sign gradient. Extensive experiments prove the effectiveness of the proposed attack method.

Overall, the proposed method on estimating the sign of the gradient for black-box attacks is novel. The authors provide sufficient analysis to present the algorithm, making it clear to see the advantage of the proposed method over previous methods. I have some minor comments on this paper.

1. In Section 2 (Line 15), the authors argue that "However, the queries are not adaptive, they are constructed based on i.i.d. random vectors {vi}". However, in Ilyas et al. (2019), the queries are designed based on the time prior, which are actually adaptive.

2. Estimating the sign of the gradient is more suitable for attacks based on the l_\infty norm, but could affect the results for l_2 attacks, since it reduces the search space. The experiments also show that the proposed method for l_2 attacks is not as effective as l_\infty attacks.

3. It's better to show some tabular results in Section 4 rather than appendix to compare the performance with numbers.
review_title: Official Blind Review #3

Meta-review: This paper presents a novel black-box adversarial attack algorithm, which exploits a sign-based rather than magnitude-based, gradient estimator for black-box optimization. It also adaptively constructs queries to estimate the gradient. The proposed approach outperforms many state-of-the-art black-box attack methods in terms of  query complexity. There is a unanimous agreement to accept this paper.
Decision: Accept (Poster)