In recent years, various studies have focused on the robustness of neural nets. While it is known that neural nets are not robust to examples with adversarially chosen perturbations as a result of linear operations on the input data, we show in this paper there could be a convex polytope within which all examples are misclassified by neural nets due to the properties of ReLU activation functions. We propose a way to find such polytopes empirically and demonstrate that such polytopes exist in practice. Furthermore, we show that such polytopes exist even after constraining the examples to be a composition of image patches, resulting in perceptibly different examples at different locations in the polytope that are all misclassified.
This paper presents an algorithm for finding a polytope of adversarial examples. This means that within a convex hull, you can move around freely and get a new adversarial example at each point, while still maintaining misclassification. It then couples this with a method of generating nearest neighbor patch-based images in an effort to create "macro-level different" examples. The premise is interesting, but the implications are questionable and I do not find the work in macro-level differences to be sound. This could be based in misunderstandings, so please let me know if you think that is the case.
Strengths:
- The notion of the polytope is interesting and the algorithm for finding such polytope seems perfectly reasonable.
- I think the goal of macro-level adversarial examples is interesting.
Weaknesses:
- First of all, the 5 corners of the polytope all look the same to me (for instance fig 2). This is not encouraging, because it means that every single point in the polytope will also look exactly like the corners. To be frank, this means the polytope is not that interesting and has only found an extremely small pocket of adversarial examples. If you use a regular method of finding a single adversarial example, I'm sure the outcome wouldn't change within some ball around the sample (perhaps with very small radius, but nonetheless). In fact, a comparison between that ball's volume and the volume of the polytope would be interesting.
- The implication of these polytopes is not at all clear if it doesn't really allow us to generate adversarial example of a new flavor. The investigation into macro-level differences does not help the case, as I will explain.
- I am not at all convinced that there is any meaning to the examples with "macro-level differences."  It's a bit unclear to me how many patches are used per image, but assuming that a patch is centered over each pixel,  it would mean that we have as many control parameters as we have pixels, which assuming the pixels each have three color values, is just 1/3 of the original degrees of freedoms. Now, the patches probably do constrain what we can paint a bit, but since the patches are applied with a pyramid, it means the center pixel will contribute more than any other for a given patch, so I'm not so sure. I'm not convinced that we can't come up with linear combinations of these patches that produce highly non-natural images with "micro-level" adversarial patterns. In fact, I think section 4.1 and figure 7 provide evidence to the contrary. Let me explain:
    - Section 4.1: Why do you need a total variation penalty at all if you have constructed a patch-based drawing method that is supposed to be unable to produce unnatural high-frequency patterns? If you only had a handful of patches and they were all non-overlapping, then this would be impressive and.
    - Figure 7: We can clearly see high-frequency patterns that create the shadow of an obelisk in 7(a). I think the same is true for "erase", although the pattern is not as recognizable. The examples actually look more suspicious than regular adversarial examples, since it looks like the original image has simply been blurred, which means the adversarial perturbations are more clear. I understand that these patterns were created using a complicated scheme of natural patches, but I think you made this method too powerful. The one interesting quality is the bottom right of the trimaran which looks like a shark - however, that is a singular occurrence in your examples and it certainly feels like the high-frequency patterns will contribute much more to class than the shark itself.
- Please let me know if I am misinterpreting the importance of the results in Figure 7, since this is an important culmination of this work.
Other comments:
- Some of notation is a bit confusing. In (1), why is p not bold but x and t are bold? They are all vectors. In Algorithm 1, x is not bold anymore.
- Algorithm 1 also seems quite unnecessary to include so explicitly.
- Isn't a bounded polytope called a "simplex"? Perhaps there is a distinction that I'm not aware of, but the absence of the word "simplex" throughout the whole paper surprised me a bit. Perhaps this is a perfectly correct omission due to differences that I'm not aware of.
Minor comments:
- abstract, "We propose a way to finding" -> either "to->"of" or "find"
- page 3, "and we can generate new colliding example" -> "a new colliding example"
- page 3, "taking arbitrary an convex combinations" -> "combination"
- page 3, "Given a target x", I think you mean "Given a target t"
- page 5, "As many gradient-based method" -> "methods"
- page 8, "carton"? "rubber"? Those are not in figure 7(b).
- page 10, "are crucial to less non-robust" ? This sentence (which is the final sentence of the conclusion and thus has a certain level of importance) is not something that is novel to your paper. The impact of non-linearities on adversarial examples have been well-studied.