Adversarial Examples Might be Avoidable: The Role of Data Concentration
  in Adversarial Robustness
Ambar Pal Jeremias Sulam René Vidal
The susceptibility of modern machine learning classifiers to adversarial
examples has motivated theoretical results suggesting that these might be
unavoidable. However, these results can be too general to be applicable to
natural data distributions. Indeed, humans are quite robust for tasks involving
vision. This apparent conflict motivates a deeper dive into the question: Are
adversarial examples truly unavoidable? In this work, we theoretically
demonstrate that a key property of the data distribution -- concentration on
small-volume subsets of the input space -- determines whether a robust
classifier exists. We further demonstrate that, for a data distribution
concentrated on a union of low-dimensional linear subspaces, exploiting data
structure naturally leads to classifiers that enjoy good robustness guarantees,
improving upon methods for provable certification in certain regimes.