Complexity theoretic limitations on learning DNF's
This work addresses the computational difficulty of learning DNF formulas and related problems for researchers in computational learning theory, but it is incremental as it builds on an existing framework to extend hardness results.
The paper shows that learning DNF formulas is hard under a natural complexity assumption related to refuting random K-SAT formulas, and this assumption also implies hardness for other learning problems like intersections of many halfspaces and agnostic learning of conjunctions.
Using the recently developed framework of [Daniely et al, 2014], we show that under a natural assumption on the complexity of refuting random K-SAT formulas, learning DNF formulas is hard. Furthermore, the same assumption implies the hardness of learning intersections of $ω(\log(n))$ halfspaces, agnostically learning conjunctions, as well as virtually all (distribution free) learning problems that were previously shown hard (under complexity assumptions).