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

<p>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 \}$.</p>

<p>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.</p>

<p>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.  <a href="http://users.soe.ucsc.edu/~manfred/pubs/J9.pdf">Occam's Razor theorem</a> 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$.</p>

<p>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.</p>

<p>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.</p>

<p><strong>UPDATE (given the changed question)</strong>:</p>

<p>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 href="http://www.mpi-inf.mpg.de/~mehlhorn/SeminarEvolvability/ValiantLearnable.pdf">A Theory of the Learnable</a>."  In fact $c$-DNF are learnable for any $c = O(1)$.</p>

<p>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)$.</p>

<p>As to whether the $n^2$ sample complexity is also a lower bound, the answer is pretty much yes.  <a href="http://www.cis.upenn.edu/~mkearns/papers/lower.ps">This paper</a> by Ehrenfeucht et al. shows that the Occam bound is almost tight.</p>

CC BY-SA 3.0
2012-01-20T15:53:20.553Z
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)?
Grigory Yaroslavtsev
CC BY-SA 3.0
2012-01-20T18:27:44.460Z
Updated the question with a reference that motivated the question.
Grigory Yaroslavtsev
CC BY-SA 3.0
2012-01-20T18:55:41.043Z
updated the answer given your updated question
Lev Reyzin
CC BY-SA 3.0
2012-01-20T18:58:00.853Z
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.
Lev Reyzin
CC BY-SA 3.0
2012-01-20T19:13:07.657Z
Thanks a lot! I will need some time to check the references, but so far it seems to be a complete answer.
Grigory Yaroslavtsev
CC BY-SA 3.0
2012-01-20T05:47:24.533Z
2012-01-20T20:53:29.137Z
2012-01-20T20:53:29.137Z
Lev Reyzin
<p>What is the state of art result about query complexity of <em>proper</em> PAC learning 2-DNF formulas <em>with sample queries</em> and <em>under uniform distribution</em>? Or any non-trivial bound on it?</p>

<p>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.</p>

<p><strong>upd.</strong> 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.</p>

<p><strong>upd.</strong> 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 efﬁciently
PAC-learnable." However, they don't mention, whether this result is for <em>proper</em> learning or give any reference.</p>

CC BY-SA 3.0
2012-01-20T04:44:09.127Z
What kind of queries?
Timothy Sun
CC BY-SA 3.0
2012-01-20T04:46:38.623Z
Just samples. Also I guess I should be explicit that the question is about query complexity, not the running time (edited).
Grigory Yaroslavtsev
CC BY-SA 3.0
2012-01-20T05:48:40.867Z
I've answered your question, assuming sample queries are just random examples (and not membership queries).
Lev Reyzin
CC BY-SA 3.0
2012-01-20T15:51:14.910Z
Yes, queries are just random examples from uniform distribution.
Grigory Yaroslavtsev
<reference-request><lg.learning><boolean-functions>
Proper PAC learning of 2-DNF under uniform distribution
Grigory Yaroslavtsev
# Proper PAC learning of 2-DNF under uniform distribution

(Asked by: username_0 on 2012-01-20)

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 efﬁciently
PAC-learnable." However, they don't mention, whether this result is for *proper* learning or give any reference.

**Tags:** reference-request, lg.learning, boolean-functions
> **Comments:**
> **username_1**: What kind of queries?  
> **username_0**: Just samples. Also I guess I should be explicit that the question is about query complexity, not the running time (edited).  
> **username_2**: I've answered your question, assuming sample queries are just random examples (and not membership queries).  
> **username_0**: Yes, queries are just random examples from uniform distribution.  

---

## 1 answers

### Answer by username_2 on 2012-01-20. Score: 14 | Accepted answer

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](http://users.soe.ucsc.edu/~manfred/pubs/J9.pdf) 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](http://www.mpi-inf.mpg.de/~mehlhorn/SeminarEvolvability/ValiantLearnable.pdf)." 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](http://www.cis.upenn.edu/~mkearns/papers/lower.ps) by Ehrenfeucht et al. shows that the Occam bound is almost tight.

> **Comments:**
> **username_0**: 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)?  
> **username_0**: Updated the question with a reference that motivated the question.  
> **username_2**: updated the answer given your updated question  
> **username_2**: 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.  
> **username_0**: Thanks a lot! I will need some time to check the references, but so far it seems to be a complete answer.  

---

