In Feldman-Gopalan-Khot-Ponnuswami 06 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?


1 Answer 1


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)


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.