Complexity Theoretic Limitations on Learning DNF's

By Amit Daniely, Shai Shalev-Shwartz. 2014

122 citations recorded by the source corpus.

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 $\omega(\log(n))$ halfspaces, agnostically learning conjunctions, as well as virtually all (distribution free) learning problems that were previously shown hard (under complexity assumptions).

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistical Learning Theory, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Yuanzhi Li
2. Zeyuan Allen-Zhu
3. Quanquan Gu
4. Simon Shaolei Du
5. Santosh Srinivas Vempala
6. John Wilmes
7. Zhao Song
8. Jason D. Lee

In Computational Theory and Mathematics

1. Zeyuan Allen-Zhu
2. Santosh Srinivas Vempala
3. John Wilmes
4. Yoav Levine
5. Amnon Shashua
6. Noam Wies
7. Zhao Song
8. Le Song

In Statistical Learning Theory

1. Yuanzhi Li
2. Zeyuan Allen-Zhu
3. Santosh Srinivas Vempala
4. John Wilmes
5. Zhao Song
6. Le Song
7. Yoav Levine
8. Amnon Shashua

In Algorithms & Complexity

1. John Wilmes
2. Santosh Srinivas Vempala
3. Zeyuan Allen-Zhu
4. Yuanzhi Li
5. Yoav Levine
6. Amnon Shashua
7. Noam Wies
8. Zhao Song

Citations in the corpus

• A Convergence Theory for Deep Learning via Over-Parameterization (2018, background): “Stronger hardness results have been proved over the last decade [13, 15, 23, 32, 37, 38, 51].”
• Complexity theoretic limitations on learning halfspaces (2015, background): “[32] A. Daniely, N. Linial, and S. Shalev-Shwartz.”
• Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks (2022, methodology): “Follows directly by combining theorem 2 and lemma 3 with either the negative results in Valiant (1984); Goldreich et al. (1986) or in Daniely & Shalev-Shwartz (2016).”
• Polynomial Convergence of Gradient Descent for Training One-Hidden-Layer Neural Networks (2018, background): “First, there are strong complexity-theoretic and cryptographic-assumption based lower bounds to contend with [5, 9, 18].”
• On the Complexity of Learning Neural Networks (2017, background): “There is much work on complexity-theoretic hardness of learning neural networks [4, 7, 15].”
• Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds (2018, background): “Moreover, there are strong complexity-theoretic and cryptographic-assumption based lower bounds to contend with [5, 9, 23].”