We introduce a new black-box attack achieving state of the art performances. Our approach is based on a new objective function, borrowing ideas from ∞ -white box attacks, and particularly designed to fit derivative-free optimization requirements. It only requires to have access to the logits of the classifier without any other information which is a more realistic scenario. Not only we introduce a new objective function, we extend previous works on black box adversarial attacks to a larger spectrum of evolution strategies and other derivative-free optimization methods. We also highlight a new intriguing property that deep neural networks are not robust to single shot tiled attacks. Our models achieve, with a budget limited to 10, 000 queries, results up to 99.2% of success rate against InceptionV3 classifier with 630 queries to the network on average in the untargeted attacks setting, which is an improvement by 90 queries of the current state of the art. In the targeted setting, we are able to reach, with a limited budget of 100, 000, 100% of success rate with a budget of 6, 662 queries on average, i.e. we need 800 queries less than the current state of the art.
This paper proposed a new query efficient black-box attack algorithm using better evolution strategies. The authors also add tiling trick to make the attack even more efficient. The experimental results show that the proposed method achieves state-of-the-art attack efficiency in black-box setting.
The paper indeed presented slightly better results than the current state-of-the-art black-box attacks. It is clearly written and easy to follow, however, the paper itself does not bring much insightful information. 
The major components of the proposed method are two things: using better evolution strategies and using tiling trick. The tiling trick is not something new, it is introduced in (Ilyas et al., 2018) and also discussed in (Moon et al., 2019). The authors further empirically studied the best choice of tiling size. I appreciated that, but will not count it as a major contribution. In terms of better evolution strategies, the authors show that (1+1) and CMA-EA can achieve better attack result but it lacks intuition/explanations why these helps, what is the difference. It would be best if the authors could provide some theories to show the advantages of the proposed method, if not, at least the authors should give more intuition/explanation/demonstrative experiments to show the advantages.
Detailed comments:
- In section 3.2, is the form of the discretized problem a standard way to transform from continuous to discrete one? What is the intuition of using a and b? Have you considered using only one variable to do it?
- In section 3.3.2 what do you mean by “with or without softmax, the optimum is at infinity”? I hope the authors could further explain it.
- In eq (2), do you mean  max_{\tau} L(f(x + \epsilon tanh(\tau)), y) ?
- In section 3.3.1, the authors said (1+1)-ES and CMA-ES can be seen as an instantiation of NES. Can the authors further elaborate on this?
- Can the authors provide algorithm for DiagonalCMA?
- It is better to put the evolution strategy algorithms in the main paper and discuss it. 
- Can the authors also comment/compare the results with the following relevant paper?
Li, Yandong, et al. "NATTACK: Learning the Distributions of Adversarial Examples for an Improved Black-Box Attack on Deep Neural Networks." ICML 2019.
Chen, Jinghui, Jinfeng Yi, and Quanquan Gu. "A Frank-Wolfe Framework for Efficient and Effective Adversarial Attacks." arXiv preprint arXiv:1811.10828 (2018).
-  In Table 1, why for Parsimonious and Bandit methods, # of tiles parts are missing? I think both of the baselines use tilting trick? And they should also run using the optimal tiling size? The result seems directly copied from the Parsimonious paper? It makes more sense to rerun it in your setting and environment cause the sampled data points may not be the same. Since CMA costs significantly more time, it makes a fair comparison to also report the attack time needed for each method.
- In Table 3, why did not compare with Bandit and Parsimonious attacks? 
======================
after the rebuttal
I thank the authors for their response but I still feel that there is a lot more to improve for this paper in terms of intuition and experiments. Therefore I decided to keep my score unchanged.