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!

  • 1
    $\begingroup$ Have you read the proofs of the two results you mention, to see what is used in the negative result of the first that doesn't apply to the positive result of the second? At a high-level: malicious noise setting, the adversary can invent points (i.e., it can modify both $x$ and its purported label $y$). In the classification noise case, it cannot modify $x$ -- but only flip $y$. $\endgroup$
    – Clement C.
    Commented Aug 2, 2017 at 19:35
  • $\begingroup$ Yes, I have read the proofs. I am sure that the bound in [1] is correct, because if $\beta \geq \frac{\epsilon}{1+\epsilon}$, then the attacker can poison the dataset in such a way that any hypothesis have the same probability of being chosen, whatever the target hypothesis is. Therefore, the PAC-learning is not accomplished (because it is required that for all target concepts and target distributions, we find an $\epsilon$-good hypothesis). What I don't get is where do they use the preservation of underlying distribution in the proof of [2]? They don't take the distribution into account. $\endgroup$
    – Cip Baetu
    Commented Aug 2, 2017 at 20:12
  • $\begingroup$ So what is the specific point that bothers you? I assume it is in the analysis of Theorem 2 of [2]? If so, have a look at how they obtain the expression for $p_i$ in the proof. In the malicious setting, these expressions don't hold anymore: the prob. that a $L_i\neq L^*$ misclassifies an example is no longer $$d_i(1-\eta)+ (1-d_i)\eta$$ since an adversary could decide (and possibly should) never to flip the label of an example falling in the complement of $L_i\Delta L^*$ (not saying it necessary would, but it would be allowed by the model). For such adv., we would have $p_i = d_i(1-\eta)$. $\endgroup$
    – Clement C.
    Commented Aug 2, 2017 at 20:26
  • $\begingroup$ (And since for the actual $L^*$ the probability of disagreement is at most $\eta$, you get $\leq \eta$ vs. $d_i(1-\eta) \geq \varepsilon(1-\eta)$. To separate the two cases, one then needs $\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, more a handwavy way to see that things are consistent.) $\endgroup$
    – Clement C.
    Commented Aug 2, 2017 at 20:32
  • $\begingroup$ That is a good point, thank you so much for stressing out! So, if there is an adversary that has the power to flip the labels (but not more than a fraction of $\beta$ of them), then there is no better upper bound for $\beta$? What about the case in which you can change the underlying distribution of the data, but you cannot flip the labels? Also, how can I upvote your response? I am newbie in using stack exchange :) $\endgroup$
    – Cip Baetu
    Commented Aug 2, 2017 at 20:38

1 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.

  • $\begingroup$ Still thinking about the second question though: How is the hypothesis that the underlying distribution of instances stays the same in case of [2] used to prove the correctness? I mean, might the underlying distribution over instances space ($\mathcal{X}$) change and the result still be viable? $\endgroup$
    – Cip Baetu
    Commented Aug 8, 2017 at 19:32
  • $\begingroup$ @tutifresh Well, by definition, $d_i$ depends on this fixed distribution. (It is the probability, under this distribution of instances, that a point falls into the region where $L_i$ and $L^\ast$ disagree.) If the distribution changes, then the whole argument that hinges on the use of $d_i$ falls apart. $\endgroup$
    – Clement C.
    Commented Aug 9, 2017 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.