The Curse of Concentration in Robust Learning: Evasion and Poisoning
  Attacks from Concentration of Measure
  Many modern machine learning classifiers are shown to be vulnerable to
adversarial perturbations of the instances. Despite a massive amount of work
focusing on making classifiers robust, the task seems quite challenging. In
this work, through a theoretical study, we investigate the adversarial risk and
robustness of classifiers and draw a connection to the well-known phenomenon of
concentration of measure in metric measure spaces. We show that if the metric
probability space of the test instance is concentrated, any classifier with
some initial constant error is inherently vulnerable to adversarial
perturbations.
  One class of concentrated metric probability spaces are the so-called Levy
families that include many natural distributions. In this special case, our
attacks only need to perturb the test instance by at most $O(\sqrt n)$ to make
it misclassified, where $n$ is the data dimension. Using our general result
about Levy instance spaces, we first recover as special case some of the
previously proved results about the existence of adversarial examples. However,
many more Levy families are known (e.g., product distribution under the Hamming
distance) for which we immediately obtain new attacks that find adversarial
examples of distance $O(\sqrt n)$.
  Finally, we show that concentration of measure for product spaces implies the
existence of forms of "poisoning" attacks in which the adversary tampers with
the training data with the goal of degrading the classifier. In particular, we
show that for any learning algorithm that uses $m$ training examples, there is
an adversary who can increase the probability of any "bad property" (e.g.,
failing on a particular test instance) that initially happens with
non-negligible probability to $\approx 1$ by substituting only $\tilde{O}(\sqrt
m)$ of the examples with other (still correctly labeled) examples.
