  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, utilizing
structure in data naturally leads to classifiers that enjoy data-dependent
polyhedral robustness guarantees, improving upon methods for provable
certification in certain regimes.
