Adversarial Machine Learning, Learning with (Malicious) noise

Question

I am reading some old papers regarding Learning With Malicious Noise. In one of them, Learning in the presence of Malicious Errors, by Kearns and Li $[1]$ (https://www.cis.upenn.edu/~mkearns/papers/malicious.pdf), it is proved that in the case that an adversary may choose a fraction $\beta \in [0, \frac{1}{2})$ of the training set to poison with instances, such that no restriction is put on the poison instances, then the upper bound $\beta < \frac{\epsilon}{\epsilon+1}$ must be met, so that it is possible to learn an $\epsilon$-good hypothesis with a probability at least $1-\delta$ (in the PAC-learning setting, using the usual notations). This bound is, however, not reached everytime, but for some specific hypothesis classes, the bound is much lower than that.

However, in the paper Learning from Noisy Examples, by Angluin and Laird $[2]$ (http://homepages.math.uic.edu/~lreyzin/f14_mcs548/angluin88b.pdf), it is shown that in the case of Clasification Noise, i.e. the attacker doesn't modify the underlying distribution of the instances, but may flip the label of some instances, with a probability $\beta$, then for every $\beta < \frac{1}{2}$, it is possible to find an $\epsilon$-good hypothesis with a probability at least $1-\delta$ (in the PAC-learning setting, using the usual notations), using at least $m \geq \frac{2}{\epsilon^2(1-2\beta)^2}\ln{\Big( \frac{2 \cdot |\mathcal{H}|} {\delta} \Big)}$ instances, where $\mathcal{H}$ is the hypothesis class supposed to be learned.

The question is: why is not possible to apply the result of $[2]$ in the case of $[1]$? How is the hypothesis that the underlying distribution of instances stays the same in case of $[2]$ used to prove the correctness? I am not able to find that in the proof. Can you please point it out for me?

Thank you so much everyone!

Answer 1

In the proof of the positive result in [2] you are referring to, namely Theorem 2, the argument goes as follows. For every possible concept $L_i$ of the hypothesis class $\mathcal{H} = \{L_1,\dots, L_N\}$, let $p_i$ to be the distance (probability of disagreement) with the true concept $L^\ast$. Then, under a classification noise $\eta$, we have that the probability $p_i$ that a labeled example $\langle x,y\rangle$ disagrees with $L^\ast$ is exactly $$ p_i = d_i(1-\eta) + (1-d_i)\eta = \eta+d_i(1-2\eta) \tag{$\dagger$} $$ where $d_i = \Pr[x\in L_i\triangle L^\ast]$ is the probability to hit the region where $L_i$ and $L^\ast$ disagree. In particular, for any "bad" concept $L_i$ which is $\varepsilon$-far from $L^\ast$, we have $p_i \geq \eta+\varepsilon(1-2\eta)$, while for $L_i=L^\ast$ we have $p_i = \eta$. The argument then goes by applying concentration bounds and a union bound over the (at most $N$) bad concepts to see how many examples are enough to ensure that, w.h.p., choosing the concept consistent with the maximum number of examples taken rules out all bad concepts. (In particular, the "gap" on expectation for $m$ examples between a bad concept and the true concept is at least $\varepsilon(1-2\eta)m$ by the above.)

Now, what changes under malicious noise? (Or, even, under the milder assumption that the adversary can, with probability $\eta$, decide to flip or not the label of a sample, instead of flipping it automatically as in the classification noise) Put it simply, $(\dagger)$ is no longer true.

For instance, the adversary could focus on a specific bad ($\varepsilon$-far) hypothesis, say $L_{i^\ast}$, and decide to only flip the label of a given example $x$ if that example falls into the region of disagreement $L_{i^\ast}\triangle L^\ast$ (and not if it doesn't). In that case, one gets $$ p_{i^\ast} = d_{i^\ast}(1-\eta) + (1-d_i)\cdot 0 = d_{i^\ast}(1-\eta) \geq \varepsilon(1-\eta) $$ instead of the previous expression. That is a huge drag for the analysis, and essentially kills it: now, in this possible scenario (which may not happen, but is a valid scenario) to have any hope of separating $L^\ast$ from this bad concept $L_{i^\ast}$ by looking at the disagreements, we need to separate the expected $\eta m$ (for $L^\ast$) from the expected $\varepsilon(1-\eta) m$ (for the bad concept $L_{i^\ast}$)... and to have any hope of doing so, we need $$ \varepsilon(1-\eta) > \eta $$ or equivalently $\eta < \frac{\varepsilon}{1+\varepsilon}$.

Note that this is by no means a formal proof of the negative result of [1], more a hand-wavy way to see that things are consistent.