Proper PAC learning of 2-DNF under uniform distribution

Question

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.

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.