Recent research has shown that machine learning systems, including state-of-the-art deep neural networks, are vulnerable to adversarial attacks. By adding to the input object an imperceptible amount of adversarial noise, it is highly likely that the classifier can be tricked into assigning the modified object to any desired class. Furthermore, these adversarial samples generalize well across models: samples generated using one network can often succeed in fooling other networks or machine learning models. These alarming properties of adversarial samples have drawn increasing interest recently, with several researchers having attributed the adversarial effect to different factors, such as the high dimensionality of the data or the overly-linear nature of modern neural networks. Nevertheless, a complete picture of the cause of adversarial samples has not yet emerged. Towards this goal, we present a novel theoretical result that formally links the adversarial vulnerability of learning to the intrinsic dimensionality of the data. In particular, our investigation formally establishes that as the local intrinsic dimensionality (LID) increases, 1-NN classifiers become increasingly prone to being subverted. We show that in expectation, a k-nearest neighbor of a test point can be transformed into its 1-nearest neighbor by adding an amount of noise that diminishes as the LID increases. We also provide an experimental validation of the impact of LID on adversarial perturbation for both synthetic and real data, and discuss the implications of our result for general classifiers.
Amsaleg et al. (Mon,) studied this question.