<p>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.)</p>

<p>Now, what changes under malicious noise? <em>(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)</em> Put it simply, $(\dagger)$ is no longer true.</p>

<p>For instance, the adversary <strong>could</strong> 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 <em>any</em> hope of doing so, we need
$$
\varepsilon(1-\eta) &gt; \eta
$$
or equivalently $\eta &lt; \frac{\varepsilon}{1+\varepsilon}$. </p>

<p>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.</p>

CC BY-SA 3.0
2017-08-08T19:32:39.993Z
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?
Cip Baetu
CC BY-SA 3.0
2017-08-09T00:08:00.557Z
@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.
Clement C.
CC BY-SA 3.0
2017-08-03T01:43:59.593Z
2017-08-03T01:43:59.593Z
Clement C.
<p>I am reading some old papers regarding Learning With Malicious Noise. In one of them, <em>Learning in the presence of Malicious Errors</em>, by Kearns and Li $[1]$ (<a href="https://www.cis.upenn.edu/~mkearns/papers/malicious.pdf" rel="nofollow noreferrer">https://www.cis.upenn.edu/~mkearns/papers/malicious.pdf</a>), 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 <strong>no restriction</strong> is put on the poison instances, then the upper bound $\beta &lt; \frac{\epsilon}{\epsilon+1}$ must be met, so that it is possible to <em>learn</em> 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.</p>

<p>However, in the paper <em>Learning from Noisy Examples</em>, by Angluin and Laird $[2]$ (<a href="http://homepages.math.uic.edu/~lreyzin/f14_mcs548/angluin88b.pdf" rel="nofollow noreferrer">http://homepages.math.uic.edu/~lreyzin/f14_mcs548/angluin88b.pdf</a>), it is shown that in the case of <em>Clasification Noise</em>, 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 &lt; \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.</p>

<p>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? </p>

<p>Thank you so much everyone! </p>

CC BY-SA 3.0
2017-08-02T19:35:28.980Z
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$.
Clement C.
CC BY-SA 3.0
2017-08-02T20:12:16.717Z
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.
Cip Baetu
CC BY-SA 3.0
2017-08-02T20:26:56.603Z
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)$.
Clement C.
CC BY-SA 3.0
2017-08-02T20:32:55.727Z
(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.)
Clement C.
CC BY-SA 3.0
2017-08-02T20:38:30.997Z
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 :)
Cip Baetu
CC BY-SA 3.0
2017-08-02T20:42:00.407Z
For the first question: I may be wrong, but I believe that indeed there is no better bound. For the second: I think it's the same, then (when something falls on $L_i \Delta L^\ast$ and you get to forge the sample, change the point so that now it's on a $x$ on which $L_i$ and $L^\ast$ agree (you cannot change the label? Change the point). For the last: you cannot, since I didn't post an answer (this is only a comment) :)
Clement C.
CC BY-SA 3.0
2017-08-02T21:06:17.373Z
That is completely true, indeed, for the steps provided by the proof in [2]. But the thing is, as long as the adversary chooses not to flip the labels, it means that the dataset is more accurate, therefore the learnability of it should be improved, am I right? If I am wrong or missing something, please point it out for me. Thank you alot for all your previous comments, brought a lot of light in my mind!
Cip Baetu
CC BY-SA 3.0
2017-08-02T21:14:03.877Z
Not necessarily: the adversary could decide that for some "bad" hypothesis of its choosing, it won't flip the labels in some cases so thatthat bad hypothesis looks better w.r.t. the examples -- but flip the label whenever possible when the example is bad for this wrong hypothesis.  It does mean more of your examples would be correctly labelled than if it flipped every time it could; but on the other hand it makes it harder to distinguish between the "right" hypothesis and this particular bad hypothesis.
Clement C.
CC BY-SA 3.0
2017-08-02T21:17:45.953Z
Makes perfect sense, thank you! Do you want to post am answer, so that I could upvote it?
Cip Baetu
CC BY-SA 3.0
2017-08-02T21:20:17.063Z
I'll try to come up with a reasonably written answer once I get back home.
Clement C.
<machine-learning><adversarial-learning>
Adversarial Machine Learning, Learning with (Malicious) noise
Cip Baetu
# Adversarial Machine Learning, Learning with (Malicious) noise

(Asked by: username_0 on 2017-08-02)

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!

**Tags:** machine-learning, adversarial-learning

> **Comments:**
> **username_1**: 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$.  
> **username_0**: 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.  
> **username_1**: 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)$.  
> **username_1**: (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.)  
> **username_0**: 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 :)  
> **username_1**: For the first question: I may be wrong, but I believe that indeed there is no better bound. For the second: I think it's the same, then (when something falls on $L_i \Delta L^\ast$ and you get to forge the sample, change the point so that now it's on a $x$ on which $L_i$ and $L^\ast$ agree (you cannot change the label? Change the point). For the last: you cannot, since I didn't post an answer (this is only a comment) :)  
> **username_0**: That is completely true, indeed, for the steps provided by the proof in [2]. But the thing is, as long as the adversary chooses not to flip the labels, it means that the dataset is more accurate, therefore the learnability of it should be improved, am I right? If I am wrong or missing something, please point it out for me. Thank you alot for all your previous comments, brought a lot of light in my mind!  
> **username_1**: Not necessarily: the adversary could decide that for some "bad" hypothesis of its choosing, it won't flip the labels in some cases so thatthat bad hypothesis looks better w.r.t. the examples -- but flip the label whenever possible when the example is bad for this wrong hypothesis.  It does mean more of your examples would be correctly labelled than if it flipped every time it could; but on the other hand it makes it harder to distinguish between the "right" hypothesis and this particular bad hypothesis.  
> **username_0**: Makes perfect sense, thank you! Do you want to post am answer, so that I could upvote it?  
> **username_1**: I'll try to come up with a reasonably written answer once I get back home.  

---

## 1 answers

### Answer by username_1 on 2017-08-03. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: @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.  

---

