Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper studies hard label adversarial attacks, to specifically examine whether such attacks find adversarial examples that are close to the data manifold. The paper argues this is counter intuitive to our current understanding that such examples leave the data manifold. The paper studies such examples in both regular and robust models on CIFAR and ImageNet datasets. I enjoyed reading the first half of the paper, but the second half and observations from the experiments were quite hard to follow because they are often vague and rely (heavily) on results from recently published work. This makes it challenging to interpret the results clearly. The plots themselves are also quite hard to read in most cases.  

Strengths:
+ Understanding the manifold traversal for zeroth order attacks is pertinent. The paper reveals an unexpected benefit for such methods, indicating that these adversarial examples may lie on the manifold, indicating that previous notions that rely explicitly on manifold-projection based strategies can fail defend against such attacks.
+ The paper presents an interesting case study of known attacks on popular benchmark recognition tasks. The central questions in the paper are interesting.
+ The results show to some degree that the variants considered in the paper (proposed by earlier papers) are closer to the manifold (under the FID measure). This improvement is exaggerated when the models are robust, which is very interesting.


Weaknesses:
* While the paper is well written overall, and easy to read, I found the language used to be imprecise which made some parts of it harder to appreciate. The paper studies an important problem, and demonstrates empirically, the benefit of using a query efficient zeroth order hard label attack, yet it seems the paper does not explain why the result is so? The observation is repeatedly referred to as unexpected, and considering it is one of the central contributions of the paper, I think it would benefit if the paper discussed the main insight into why such an observation occurred in the first place, and more importantly what it tells us about adversarial attacks. 
* Too many details are left out of the paper, which make the exact contributions of this work harder to understand. For example, there is only a brief mention of the mapping functions like an AE or a BiLIN or how they are used in this context. How is the BiLIN used here? The reduced dimension ZO search is already shown to be more query efficient in Tu et al (2019). Why do BiLIN variants exploit reduced resolution better?
* Is the finding Q3 of this paper or from Tu et al. (2019)? What new insight does the present manuscript bring that Tu et al (2019) do not have?
* Why is FID the right manifold distance measure? It would greatly help if the observation that query efficient ZO attacks find on-manifold samples, was validated independently outside the FID measure. In other words, does this attack render “manifold projection” based defenses useless? If the sample is already on or close to the manifold, in theory these attacks would be exactly reproduced under a manifold-projection defense?
* The explanations of CIFAR-10 results could be expanded further, it is not clear why AE+Sign-OPT does worse. What does the similarities of the FID curves imply? In general, I think it would help if the paper made more explicit what were to be inferred from these plots. They are also hard to read (perhaps a log axis would help?)
* What is the success rate for these attacks? This is only provided in the supplement, but the experiments section refers to them. It would help if they were in the main text as well. 
* Some editorial comments: I would recommend taking some of the explanations for BiLIN outperforming AE variants to motivate its use earlier when it is introduced itself.
* in Section 5 “the manifold can be leaked by the loss landscape” what does this mean exactly?  



----------- Update after revision ---------------------

Dear Authors, 

Thank you for the revised manuscript. The expanded sections have helped me understand the paper more deeply, and place the contributions in context to prior work better than before. I especially appreciate the new experiments and explanations on the Robust Manifold Defense. 

A few comments on the revised paper: 

* First, the success rate plots which were missing are quite revealing: While the biggest benefit of the reduced resolution query search appears to have been in robust models (Madry et al), the benefit is not reflected as clear in terms of the success rates (which is arguably more critical). For example, in CIFAR-10 experiment in Fig 2(a) while in the Natural case, BiLN+HSJA is slightly more query efficient it appears less successful than plain HSJA in Fig 6(a). (Once again, the plots and figures are extremely illegible). 
* For "Robust" CIFAR-10 models and "Natural" ImageNet , there appears to be a considerable gain in both $L_\infty $ distortion *and* success-rate.  For the "Robust" ImageNet case, while there are *huge* gains in terms of $L_\infty $ distortion, there is essentially no discernible difference in the success rate between reduced-resolution and the original attacks. 
* by the way there appears to be a typo in Fig 6(a): both BiLN+Sign-OPT and AE+SignOPT are the same color in the plot
* In the new Figure 4 with MNIST experiments, in all the experiments, the base attack appears to be more query efficient than the resolution reduced attack. For a few it appears that before 5000 queries the reduced-resolution are better, but claiming this supports the earlier results isn't as convincing.  
* The observations from these plots are confusing: 
>"The hard-label attacks consistently outperform against the Robust Manifold defense": 
Again not clear how it is claimed that the attack is outperforming the defense without mentioning success rates for this experiment. This also does not clearly outline why the reduced-resolution variants to not match up to the base attacks?
* The reconstruction error plots are also very hard to see -- once again all the reduced-resolution suffer in these experiments. The explanation given is that:
> "Due to the dynamics of the topological hierarchy discussed before, the dimension-reduction is less effective on MNIST" 
This is another example of very heavy terminology that makes it hard to understand what the argument is exactly. 

Overall, I think the paper needs more clarity in its experiments. The story is muddled by several inconsistent results, some showing improvements with reduced resolution (the finding is surprising and genuinely interesting.. but unfortunately doesn't seem to be consistent; especially when looking at it with the success rate metric)

I think the authors have a convincing motivation and argument that query-efficient hard label attacks achieved with reduced-resolution can be closer to the manifold, this is clear in Robust CIFAR-10, Natural ImageNet models. The paper does a good job of explaining why these are the case, unfortunately the hypothesis doesn't hold up just as well in the other scenarios, which raises the question as to how these can be used in a more realistic scenario -- and more importantly as one of the other reviewers also pointed out -- what the reader must take out of these results to appreciate query efficient attacks better. I think in its current state the experiments portray a more confusing picture than the arguments in the paper suggest. As a result, I will retain my original score. 



review_title: Paper with interesting empirical observations but lacking clear, precise explanations and insights 

final_score: rating: 3: Clear rejection
review_content: #### Major Issues:
1. The biggest problem is, the author claimed "super-pixels help eliminate the search space of off-manifold adversarial
examples, leading to examples which are truly generalization errors" in the introduction, but never provide convincing proofs for this argument. The analysis in Section 3 is basically based on intuition and is full of holes.
2. It is very obvious that the authors do not have enough time to polish this paper. This problem is even more obvious in the later parts of this work. To name a few: (a) in the contribution part of Section1, the sub-title is missing for the third part. (b) in Section 3.3, the author first term bilinear transformation as BiLIN but refer it as BiLN in later parts. (c) Some notations are absent or inconsistend. For example, the $u_i$ vector in Equation 2 is first denoted as $u_j$. BTW, what does $\beta$ represents? (d) The information provided by the images is very unclear. What does the column of "CIFAR10/ImageNet" represents? Standard training? This makes the reviewer can not catch the main idea of the work. Even after reading this paper, I still do not understand what method has the author proposed as they claimed in their third contribution.
3. The author claimed in the third contribution of their work that their method can encourage on-manifold examples. How will this help improving robustness? Will this decrease the generalization errors?

#### Minor Issues:
1. In Sec 3.4, the author wrote: "Thus, we are interested in the tradeoff between query
efficiency and search fidelity. This introduces our central research question: How does searching over
reduced-dimension increase efficiency, if the search resolution is decreased as a side-effect?" What is the answer to this question. BTW, the author never mention this "trade-off" part in the introduction, which seems very abrupt to me.
2. The Q&A in Sec 4.1 are redundant. It basically rephrase the content in the three contribution.
3. Why select FID-64? How about features in other depth?
review_title: Incomplete work with unclear motivation and poor writing

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary
-------------
The paper investigates methods that perform hard-label adversarial attacks at the zeroth-order and analyze them from the perspective of generating on-manifold adversarial examples, down-scaling of the input space, and query-efficiency on two datasets, cifar and imagenet.


Pros
------
- The paper is well written.
- The paper tries to address a very important topic of adversarial attacks.
- The paper provides some interesting insights on dimension-reduced attacks, query efficiency and reduced resolution for current methods that use zeroth-order hard-label attacks.

Cons
-------
- Although the insights are interesting, it  is not clear how they can be used to design a new SOTA algorithm that outperforms OPT-Attack,  Sign-OPT, and RayS in terms of identifying an adversarial example with smaller distortion with less queries. This seems to be  a big weakness of this work as the experiments comparing the existing methods are not comprehensive enough to help advance the field of designing better adversarial attacks and ways to counter them.

- It is not clear the claim that down-scaling techniques would lead to worse (farther-away) adversarial examples.

- It is not clear why FID is a good measure for determining whether an adversarial example is an on-manifold example.

- No success rates vs query plots like in [1] which is common in the  literature.

- Code is not provided to verify the results

- It doesn't seem like there were multiple runs of the experiments. It is important to have multiple runs and report the mean and std to get more reliable results.

- Lacks method. The paper does not propose a new method. Instead it compares between few existing methods and makes non-impactful insights on their behavior.

Conclusion
---------------
Although the paper is well written and the insights are interesting, it doesn't seem they are impactful enough to be publishable in ICLR. 

However, if the authors convince me otherwise about the impact of these insights in the rebuttal period  I will be happy to increase the score.

Post-rebuttal 
------------------

I appreciate the response and the manuscript update, but some of the comments have not been addressed such as the code which has not been provided, and the fact that the results are still very inconsistent like R2 mentioned although the arguments made in this work seem clearer to me. But it is still not clear to me how the results can be used to improve current methods for identifying adversarial examples with smaller distortion and less queries. Thus, I will retain my score as is. 

[1] SIGN-OPT: A QUERY-EFFICIENT HARD-LABEL ADVERSARIAL ATTACK. ICLR2020
review_title: Interesting findings but are they impactful?

Meta-review: The paper investigates several properties of adversarial examples obtained by hard-label attacks. There are some interesting findings in this paper, such as the connection between query efficiency and distance to the image manifold. However, all the reviewers think the paper is below the acceptance threshold due to several weaknesses, including insufficient experiments, clarity, and whether the observations made in the paper can benefit query efficiency or quality of hard-label attacks. 
Decision: Reject