A general lower bound on the number of examples needed for learning
A general lower bound on the number of examples needed for learning
A. Ehrenfeucht,D. Haussler,M. Kearns,L. Valiant
1988 · DOI: 10.1016/0890-5401(89)90002-3
Annual Conference Computational Learning Theory · 534 Citations
TLDR
This paper proves a lower bound on the number of random examples required for distribution-free learning of a concept class C and shows that for many interesting concept classes, including k CNF and k DNF, the bound is actually tight to within a constant factor.