We present a novel black-box adversarial attack algorithm with state-of-the-art model evasion rates for query efficiency under ∞ and 2 metrics. It exploits a sign-based, rather than magnitude-based, gradient estimation approach that shifts the gradient estimation from continuous to binary black-box optimization. It adaptively constructs queries to estimate the gradient, one query relying upon the previous, rather than re-estimating the gradient each step with random query construction. Its reliance on sign bits yields a smaller memory footprint and it requires neither hyperparameter tuning or dimensionality reduction. Further, its theoretical performance is guaranteed and it can characterize adversarial subspaces better than white-box gradient-aligned subspaces. On two public black-box attack challenges and a model robustly trained against transfer attacks, the algorithm's evasion rates surpass all submitted attacks. For a suite of published models, the algorithm is 3.8× less failure-prone while spending 2.5× fewer queries versus the best combination of state of art algorithms. For example, it evades a standard MNIST model using just 12 queries on average. Similar performance is observed on a standard IMAGENET model with an average of 579 queries.
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).