<p>Let me clarify the question a bit first:
Agnostic learning conjunctions is known to be NP-hard only if the learner needs to be proper (output a conjunctions as a hypothesis) and work for any input distribution. The reductions in FGKP06 are for the uniform distribution and to the best of my knowledge there is no similar result for general distributions.
But in either case the answer to your question is "no" (in the sense that such a reduction is not known and unlikely to exist).
Learning conjunctions with random (classification) noise is an easy problem that was solved in a paper of Anguin and Laird "Learning From Noisy Examples" from 1988 that introduced the model of random noise (see also Kearns 1993 paper on Statistical Queries)
Learning conjunctions with malicious noise is at least as hard as agnostic learning of conjunctions which is believed to be a hard problem (even over the uniform distribution it is at least as hard as learning log-n sparse parities with noise)</p>

CC BY-SA 3.0
2015-03-24T18:30:52.543Z
2015-03-25T05:26:30.857Z
2015-03-25T05:26:30.857Z
Vitaly
<p>In <a href="http://research.microsoft.com/pubs/77673/hs-parity-monomial_SIAM.pdf">Feldman-Gopalan-Khot-Ponnuswami 06</a> the authors show that agnostically learning parities reduces to learning parities with random classification noise. They also remark (among other things) that learning conjunctions in this model is NP-hard. </p>

<p>Though I can't remember the source right now, I also recall that a random projection argument gives a reduction from learning parities with malicious noise to learning parities with uniform random noise.</p>

<p>Is there a reduction from learning conjunctions with malicious noise to learning conjunctions with random noise?</p>

<lg.learning><reductions>
Does learning conjunctions with malicious noise reduce to learning conjunctions with random noise?
Jeremy Kun
# Does learning conjunctions with malicious noise reduce to learning conjunctions with random noise?

(Asked by: username_0 on 2015-03-24)

In [Feldman-Gopalan-Khot-Ponnuswami 06](http://research.microsoft.com/pubs/77673/hs-parity-monomial_SIAM.pdf) the authors show that agnostically learning parities reduces to learning parities with random classification noise. They also remark (among other things) that learning conjunctions in this model is NP-hard.

Though I can't remember the source right now, I also recall that a random projection argument gives a reduction from learning parities with malicious noise to learning parities with uniform random noise.

Is there a reduction from learning conjunctions with malicious noise to learning conjunctions with random noise?

**Tags:** lg.learning, reductions


---

## 1 answers

### Answer by username_1 on 2015-03-24. Score: 9 | Accepted answer

Let me clarify the question a bit first:
Agnostic learning conjunctions is known to be NP-hard only if the learner needs to be proper (output a conjunctions as a hypothesis) and work for any input distribution. The reductions in FGKP06 are for the uniform distribution and to the best of my knowledge there is no similar result for general distributions.
But in either case the answer to your question is "no" (in the sense that such a reduction is not known and unlikely to exist).
Learning conjunctions with random (classification) noise is an easy problem that was solved in a paper of Anguin and Laird "Learning From Noisy Examples" from 1988 that introduced the model of random noise (see also Kearns 1993 paper on Statistical Queries)
Learning conjunctions with malicious noise is at least as hard as agnostic learning of conjunctions which is believed to be a hard problem (even over the uniform distribution it is at least as hard as learning log-n sparse parities with noise)


---

