  We study the problem of robust learning under clean-label data-poisoning
attacks, where the attacker injects (an arbitrary set of) correctly-labeled
examples to the training set to fool the algorithm into making mistakes on
specific test instances at test time. The learning goal is to minimize the
attackable rate (the probability mass of attackable test instances), which is
more difficult than optimal PAC learning. As we show, any robust algorithm with
diminishing attackable rate can achieve the optimal dependence on $\epsilon$ in
its PAC sample complexity, i.e., $O(1/\epsilon)$. On the other hand, the
attackable rate might be large even for some optimal PAC learners, e.g., SVM
for linear classifiers. Furthermore, we show that the class of linear
hypotheses is not robustly learnable when the data distribution has zero margin
and is robustly learnable in the case of positive margin but requires sample
complexity exponential in the dimension. For a general hypothesis class with
bounded VC dimension, if the attacker is limited to add at most $t>0$ poison
examples, the optimal robust learning sample complexity grows almost linearly
with $t$.
