Adversarial Robustness May Be at Odds With Simplicity
  Current techniques in machine learning are so far are unable to learn
classifiers that are robust to adversarial perturbations. However, they are
able to learn non-robust classifiers with very high accuracy, even in the
presence of random perturbations. Towards explaining this gap, we highlight the
hypothesis that $\textit{robust classification may require more complex
classifiers (i.e. more capacity) than standard classification.}$
  In this note, we show that this hypothesis is indeed possible, by giving
several theoretical examples of classification tasks and sets of "simple"
classifiers for which: (1) There exists a simple classifier with high standard
accuracy, and also high accuracy under random $\ell_\infty$ noise. (2) Any
simple classifier is not robust: it must have high adversarial loss with
$\ell_\infty$ perturbations. (3) Robust classification is possible, but only
with more complex classifiers (exponentially more complex, in some examples).
  Moreover, $\textit{there is a quantitative trade-off between robustness and
standard accuracy among simple classifiers.}$ This suggests an alternate
explanation of this phenomenon, which appears in practice: the tradeoff may
occur not because the classification task inherently requires such a tradeoff
(as in [Tsipras-Santurkar-Engstrom-Turner-Madry `18]), but because the
structure of our current classifiers imposes such a tradeoff.
