Is sample complexity of PAC learning all $k$-DNFs over the uniform distribution known (that is all DNFs with all terms of size at most $k$ and without restriction on the number of terms)? The only bounds I'm aware of are

  1. the obvious upper bound of $O(n^k/\epsilon)$ (which is true even for distribution independent learning)
  2. the obvious lower bound of $\Omega(2^k)$ (even for a constant $\epsilon$).
  3. the upper bound of $\tilde{O}(k^{k \log{1/\epsilon}})$ which is implied by Mansour's (1992) paper on learning DNF (the algorithm there uses membership queries but the structural result can also be used to get a sample upper bound).

I'm primarily interested in lower bounds. Also, anyone knows anything interesting about the same question for monotone $k$-DNF? For this case I don't know if even the trivial lower bound is true. Although slightly weaker bounds can be obtained by scaling lower bounds for learning monotone functions from Blum-Birch-Langford paper.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.