What is the state of art result about query complexity of proper PAC learning 2-DNF formulas with sample queries and under uniform distribution? Or any non-trivial bound on it?

Because I am not familiar at all with learning theory and this question is motivated by a different field, the answer might be obvious. I checked the book by Kearns and Vazirani, but they don't seem to consider this setting explicitly.

upd. Although the main parameter of interest is query complexity, running time is also important. If possible, running time should preferably be roughly the same as query complexity or at most polynomial.

upd. Appendix B (top of the page 18) of the paper "Learning Submodular Functions" by Balcan and Harvey mentions that "It is well known that 2-DNFs are efficiently PAC-learnable." However, they don't mention, whether this result is for proper learning or give any reference.

  • $\begingroup$ What kind of queries? $\endgroup$ Jan 20, 2012 at 4:44
  • $\begingroup$ Just samples. Also I guess I should be explicit that the question is about query complexity, not the running time (edited). $\endgroup$ Jan 20, 2012 at 4:46
  • $\begingroup$ I've answered your question, assuming sample queries are just random examples (and not membership queries). $\endgroup$
    – Lev Reyzin
    Jan 20, 2012 at 5:48
  • 1
    $\begingroup$ Yes, queries are just random examples from uniform distribution. $\endgroup$ Jan 20, 2012 at 15:51

1 Answer 1


I don't know if you'll consider the following a non-trivial bound, but here I go.

First, to be clear so that we're not confusing $c$-DNF with $k$-term DNF (which I often do), an $c$-DNF formula over variables $x_1, \ldots, x_n$ is of the form $\vee_{i=1}^{k}(\ell_{i,1} \wedge \ell_{i,2} ... \ell_{i,c})$ where $\forall 1 \le i \le k$ and $1 \le j \le c$, $\ell_{i,j} \in \{x_1, \ldots, x_n, \bar{x}_1, \ldots, \bar{x}_n \}$.

We can first ask how many distinct terms can exist in an $c$-DNF. Each term will have $c$ of the $n$ variables, each either negated or not -- making for $2^c\binom{n}{c}$ different possible terms. In a 2-DNF instance, each term will either appear or not, making for $|\mathcal{H}| = 2^{2^c\binom{n}{c}}$ possible "targets," where $\mathcal{H}$ is the hypothesis space.

Imagine an algorithm that takes $m$ samples and then tries all of the $|\mathcal{H}|$ hypotheses until it finds one that predicts perfectly on the samples. Occam's Razor theorem says that you only need to take about $m = O(\frac{1}{\epsilon}|(\mathcal{H}|+\frac{1}{\delta})$ samples for this algorithm to find a target with error $\le \epsilon$ with probability $\ge 1-\delta$.

In our case, for $c=2$, $\lg|\mathcal{H}| = O(n^2)$, which means you'll need about $n^2$ samples to do the (proper) learning.

But the whole game in learning is not really sample complexity (though that's part of the game, especially in attribute-efficient learning), but rather in trying to design polynomial-time algorithms. If you don't care about efficiency, then $n^2$ is the simplest answer for PAC sample complexity.

UPDATE (given the changed question):

Because you explicitly stated that you only cared about sample complexity, I presented the brute-force Occam Algorithm, which is the probably the simplest argument. However, my answer was a bit coy. $2$-DNF are actually learnable in polynomial time! This is a result from Valiant's original paper, "A Theory of the Learnable." In fact $c$-DNF are learnable for any $c = O(1)$.

The argument goes as follows. You can view a $c$-DNF as a disjunction of $\approx n^c$ "meta-variables" and try to learn the disjunction by eliminating the meta-variables inconsistent with the examples. Such a solution can be easily translated back to a "proper" solution, and takes $O(n^c)$ time. As a side-note, it is still open whether there is polynomial-time algorithm for $c = \omega(1)$.

As to whether the $n^2$ sample complexity is also a lower bound, the answer is pretty much yes. This paper by Ehrenfeucht et al. shows that the Occam bound is almost tight.

  • 1
    $\begingroup$ Thank you! This is a non-trivial result -- I didn't realize that exponential running time will be helpful. However, for the application I have in mind actually polynomial time is much more desirable (updated the question). Is the approach you described the best known for this problem? Are there any lower bounds on query complexity (even for unbounded running time)? $\endgroup$ Jan 20, 2012 at 15:53
  • $\begingroup$ Updated the question with a reference that motivated the question. $\endgroup$ Jan 20, 2012 at 18:27
  • 1
    $\begingroup$ updated the answer given your updated question $\endgroup$
    – Lev Reyzin
    Jan 20, 2012 at 18:55
  • $\begingroup$ Also -- in this case, I don't think exponential running time is helpful. But in general, it seems to be. Learning (with optimal sample complexity) is usually easy when you have exponential time. $\endgroup$
    – Lev Reyzin
    Jan 20, 2012 at 18:58
  • 2
    $\begingroup$ Thanks a lot! I will need some time to check the references, but so far it seems to be a complete answer. $\endgroup$ Jan 20, 2012 at 19:13

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.