Over the past four years, neural networks have been proven vulnerable to adversarial images: targeted but imperceptible image perturbations lead to drastically different predictions. We show that adversarial vulnerability increases with the gradients of the training objective when viewed as a function of the inputs. For most current network architectures, we prove that the 1 -norm of these gradients grows as the square root of the input size. These nets therefore become increasingly vulnerable with growing image size. Our proofs rely on the network's weight distribution at initialization, but extensive experiments confirm that our conclusions still hold after usual training.
This paper argues that adversarial vulnerability of neural networks increases with input dimension. Theoretical and empirical evidence are given which connect the l_p norm of the gradient of the training objective with the existence of small-worst case l_q perturbations. This connection is made by assuming that the learned function is well approximated by a linear function local to the sampled input x. By making assumptions on the initialization scheme for some simple architectures, the authors show that the l_p norm of the gradient for randomly initialized network will be large, and provide empirical evidence that these assumptions hold after training. These assumptions imply bounds on the typical magnitude of the gradient of the loss with respect to a single input coordinate, this then implies that the overall gradient norm will depend on the input dimension.
I found this paper well written. The mathematical assumptions are presented in a clear, easy to understand manner. Also high level intuition is given around their main theorems which help the reader understand the main ideas. However, I have a  number of concerns about this work.
The first is, I do not buy the motivation for studying the "phenomenon" of small worst-case l_p perturbations. I realize this statement applies to a large body of literature, but since the publication of  [1] we are still lacking concrete motivating scenarios for the l_p action space. I would encourage the authors instead to ask the closely related but more general question of how we can improve model generalization outside the natural distribution of images, such as generalization in the presence of commonly occurring image corruptions [2]. It's possible that the analysis in this work could better our understanding model generalization in the presence of different image corruptions, indeed by making similar linearity assumptions as considered in this work, test error in additive Gaussian noise can be linked with distance to the decision boundary [3,4]. However, this particular question was not explored in this work.
Second, the work is one of many to relate the norm of the gradient with adversarial robustness (for example, this has been proposed as a defense mechanism in [5,6]). I also suspect that the main theorem relating gradient norm to initialization should easily follow for more general settings using the mean field theory developed by [7,8] (this would be particularly useful for removing assumption H1, which assumes the ReLU activation is a random variable independent of the weights). Overall, I don't see how gradient norms explain why statistical classifiers make mistakes, particularly for more realistic attacker action spaces [9]. Even for "small" l_p adversarial examples there seem to be limitations as to how much gradient norms can explain the phenomenon --- for example even max margin classifiers such as SVM's have "adversarial examples". Furthermore, adversarial training has been shown to reach a point where the model is "robust" locally to training points but this robustness does not generalize to the points in the test set [10]. In fact, for the synthetic data distributions considered in [10], it's proven that no learning algorithm can achieve robustness given insufficient training data.
Finally, the main conclusion of this work "adversarial vulnerability of neural networks increases with input dimension" is an overly general statement which needs a much more nuanced view. While experiments shown in [11] support this conclusion for naturally trained networks, it is shown that when adversarial training is applied the model is more robust when the input dimension is higher (see Figure 4 a. and b.). Perhaps the assumptions for Theorem 4 are violated for these adversarially trained models. 
1. https://arxiv.org/abs/1807.06732
2. https://arxiv.org/abs/1807.01697
3. https://arxiv.org/abs/1608.08967
4. https://openreview.net/forum?id=S1xoy3CcYX&noteId=BklKxJBF57.
5. https://arxiv.org/abs/1704.08847
6. https://arxiv.org/abs/1608.07690
7. https://arxiv.org/abs/1611.01232
8. https://arxiv.org/abs/1806.05393
9. https://arxiv.org/abs/1712.09665
10. https://arxiv.org/abs/1804.11285
11. https://arxiv.org/pdf/1809.02104.pdf