7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.