PRIOR CONVICTIONS: BLACK-BOX ADVERSARIAL ATTACKS WITH BANDITS AND PRIORS
We study the problem of generating adversarial examples in a black-box setting in which only loss-oracle access to a model is available. We introduce a framework that conceptually unifies much of the existing work on black-box attacks, and we demonstrate that the current state-of-the-art methods are optimal in a natural sense. Despite this optimality, we show how to improve black-box attacks by bringing a new element into the problem: gradient priors. We give a bandit optimization-based algorithm that allows us to seamlessly integrate any such priors, and we explicitly identify and incorporate two examples. The resulting methods use two to four times fewer queries and fail two to five times less than the current state-of-the-art.
This paper formulates the black-box adversarial attack as a gradient estimation
problem, and provide some theoretical analysis to show the optimality of an
existing gradient estimation method (Neural Evolution Strategies) for black-box
attacks.
This paper also proposes two additional methods to reduce the number of queries
in black-box attack, by exploiting the spacial and temporal correlations in
gradients. They consider these techniques as priors to gradients, and a bandit
optimization based method is proposed to update these priors. 
The ideas used in this paper are not entirely new. For example, the main
gradient estimation method is the same as NES (Ilyas et al. 2017);
data-dependent priors using spatially local similarities was used in Chen et
al. 2017.  But I have no concern with this and the nice thing of this paper is 
to put these tricks under an unified theoretical framework, which I really 
appreciate.
Experiments on black-box attacks to Inception-v3 model show that the proposed
bandit based attack can significantly reduces the number of queries (2-4 times
fewer) when compared with NES. 
Overall, the paper is well written and ideas are well presented.
I have a few concerns:
1) In Figure 2, the authors show that there are strong correlations between the
gradients of current and previous steps. Such correlation heavily depends on
the selection of step size.  Imagine that the step size is sufficiently large,
such that when we arrive at a new point for the next iteration, the
optimization landscape is sufficiently changed and the new gradient is vastly
different than the previous one. On the other hand, when using a very small
step-size close to 0, gradients between consecutive steps will be almost the
same. By changing step-size I can show any degree of correlation.  I am not
sure if the improvement of Bandit_T comes from a specific selection of
step-size. More empirical evidence on this need to be shown - for example, run
Bandit_T and NES with different step sizes and observe the number of queries
required.
2) This paper did not compare with many other recent works which claim to
reduce query numbers significantly in black-box attack. For example, [1]
proposes "random feature grouping" and use PCA for reducing queries, and [2]
uses a good gradient estimator with autoencoder. I believe the proposed method
can beat them, but the authors should include at least one more baseline to 
convince the readers that the proposed method is indeed a state-of-the-art.
3) Additionally, the results in this paper are only shown on a single model
(Inception-v3), and it is hard to compare the results directly with many other
recent works. I suggest adding at least two more models for comparison (most
black-box attack papers also include MNIST and CIFAR, which should be easy to
add quickly). These numbers can be put in appendix.
Overall, this is a great paper, offering good insights on black-box adversarial
attack and provide some interesting theoretical analysis. However currently it
is still missing some important experimental results as mentioned above, and
not ready to be published as a high quality conference paper. I conditionally
accept this paper as long as sufficient experiments can be added during the
discussion period.
[1] Exploring the Space of Black-box Attacks on Deep Neural Networks, by Arjun
Nitin Bhagoji, Warren He, Bo Li and Dawn Song, https://arxiv.org/abs/1712.09491
(conference version accepted by ECCV 2018)
[2] AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking
Black-box Neural Networks, by Chun-Chen Tu, Paishun Ting, Pin-Yu Chen, Sijia
Liu, Huan Zhang, Jinfeng Yi, Cho-Jui Hsieh, Shin-Ming Cheng,
https://arxiv.org/abs/1805.11770
==========================================
After discussing with the authors, they provided better evidence to support the conclusions in this paper, and fixed bugs in experiments. The paper looks much better than before. Thus I increased my rating.