A wide range of defenses have been proposed to harden neural networks against adversarial attacks. However, a pattern has emerged in which the majority of adversarial defenses are quickly broken by new attacks. Given the lack of success at generating robust defenses, we are led to ask a fundamental question: Are adversarial attacks inevitable? This paper analyzes adversarial examples from a theoretical perspective, and identifies fundamental bounds on the susceptibility of a classifier to adversarial attacks. We show that, for certain classes of problems, adversarial examples are inescapable. Using experiments, we explore the implications of theoretical guarantees for real-world problems and discuss how factors such as dimensionality and image complexity limit a classifier's robustness against adversarial examples.
This paper explores the inevitability of adversarial examples with concentration inequalities. It is motivated by the difficulties of achieving adversarial robustness in literature. It derives isoperimetric inequalities on a cube, and then discuss the adversarial robustness of data distributed inside the cube, with the assumption that the data has bounded density. These inequalities are established on different norms. The authors then discuss limitation of the proposed bounds when analyzing practical data distribution and discussed the influence of dimensionality on adversarial robustness.
Novelty of the idea:
The idea of using concentration inequalities to explain vulnerability is novel in the field of adversarial examples and is a relevant/meaningful angle on understanding this phenomenon. (Although there are concurrent works also relating concentration inequalities to adversarial robustness, they don't diminish the novelty of this work.)
On technical contributions:
In summary, this paper applies / adapts previous results in concentration inequalities to develop bounds related to adversarial examples. The bounds in Lemma 3 are on any p>0, this seems to be new to my knowledge, but the technical contribution in the proof is limited.
Here are some detailed comments.
The authors claim that
"This question is complicated by the fact that simple, geometric isoperimetric inequalities fail to exist for the cube, and the shapes that achieve minimal \eps-expansion (if they exist) depend on the volume they enclose and the choice of \eps."
This statement is at least misleading, if not wrong. It is well known that geometric isoperimetric inequality does exist for cube for the L2 case (see Ledoux, M., 2001. Proposition 2.8.), and the proof procedure the author used is also very similar to the proofs in Ledoux, M., 2001.
Theorem 5's proof is confusing, if not wrong. 
This is my brief recap on the first part of Thm 5, 
If there exists eps and p such that, for all classifiers on MNIST, a random image has eps-adv with probability at least p, then for all classifiers on b-MNIST, a random image has b*eps-adv with probability at least p.
The proof in Appendix E says b-MNIST images can be classified by first downsampling. These downsampled classifiers do not cover "all classifiers on b-MNIST", so I don't see how the proof stands.
Likewise, the proof of the second part has the similar problem.
Therefore, I'm not yet convinced that Thm 5 is correct.
Also I suggest the authors use more rigorous language to present Theorem 5, in a similar fashion to previous theorems.
Re: Lemma 4, my understanding is that it is from previous literature. The authors should point out exactly where is it from (with section# and theorem#), so that readers and reviewers can more easily check the correctness of it.
The authors mention that "Intuitively, the concentration limit Uc can be interpreted as a measure of image complexity."
I think this statement is problematic. It is, at best, oversimplifying the the problem. If we assume the data lies in low-dimensional space, the volume of the support will be 0, no matter how complex the shape of the manifold is. This lead to unbounded density in the ambient dimension.
Even when considering "expanded dataset" like the authors discussed in Section 7, it is not obvious that Uc can be interpreted as image complexity. To make such a claim, more assumptions need to made and more analyses need to be done.
Similar comments applies to the "correlations between pixels" and concentration.
On the significance:
As the author themselves have already mentioned, the bounds described in the paper all depends on the bounded density of the data distribution. In practice, the density of data distribution is difficult to understand, if not impossible. Therefore it is still inconclusive whether the "inevitability" exists. But to be fair, I believe this is mostly due to the difficulty of the problem being studied.
Clarity and writing:
The skeleton of the paper is well written and easy to follow. I've pointed out some problems in my previous comments.
I also appreciate that the authors made efforts to not overclaim.
here are a few more comments:
- I personally feel Section 3 as an "warm-up" section is redundant, and the authors can consider move them to the appendix.
- In Section 6 and 7, the authors talk about when is the bound "meaningful" and "active". This part is confusing/misleading. eps=sqrt(n) is actually the maximum possible perturbation and not falls into the common "adversarial perturbation" where the perturbation does not change the semantic meaning of the image. There should be a least an additional numerical examples on small eps, so the readers have better ideas on the tightness/looseness of the bound.
References:
Ledoux, M., 2001. The concentration of measure phenomenon (No. 89). American Mathematical Soc..
==========================
I change my rating on this paper to be 6, after the authors' response.