<p>Yes, some lower bounds are known. For example, assuming $NP \neq coNP$, you cannot even properly learn read-thrice DNF formulas in polynomial time.  There is a whole <a href="http://dl.acm.org/citation.cfm?id=296694" rel="nofollow noreferrer">paper</a> developing such hardness results using something called the "representation problem".</p>

<p>To answer your linked-to question: Schapire, in his <a href="http://dl.acm.org/citation.cfm?id=136314" rel="nofollow noreferrer">dissertation</a>, in addition to proving that "weak learning" = "strong learning," also improved on Angluin's bound and gave an algorithm that uses $O(n)$ equivalence queries and $O(n^2+ n \log m)$ membership queries for learning DFA.</p>

<p>One easy way to get lower bounds is information-theory.  You can figure out how many distinct targets there are and how many bits a query gives you, etc.  These upper bounds come close but aren't there.  There are also issues one needs to think about regarding how the "counterexamples" arrive to the learner.  A well-chosen counterexample can give away quite a lot of information.</p>

<p><em>Update to the discussion above</em>: Angluin and Dohrn address the question learning with random counterexamples in a <a href="http://proceedings.mlr.press/v76/angluin17a/angluin17a.pdf" rel="nofollow noreferrer">recent paper</a>.</p>

CC BY-SA 3.0
2012-04-03T18:57:40.460Z
Thanks for the answer! Do you mind if I give your answer to my linked question on the linked question (with links back here)? Or do you plan to make a CS.SE account? I totally agree with paragraph 3, I was fooling around with demanding that the tutor give a minimal counterexample and learning seems to become much easier.
Artem Kaznatcheev
CC BY-SA 3.0
2012-04-03T21:05:05.120Z
No problem! And feel free to post to the linked CS.SE question.
Lev Reyzin
CC BY-SA 3.0
2012-04-04T03:11:43.383Z
I read through the relevant part of Schapire's thesis (section 5.4.5) and [summarized the improvement](http://cs.stackexchange.com/a/1021/55), hopefully I got the gist right. I will look more closely at the lower-bounds paper you cite later in the week :D.
Artem Kaznatcheev
CC BY-SA 3.0
2012-04-05T17:42:52.583Z
Cool. I'd upvote it if I had a CS.SE account :)
Lev Reyzin
CC BY-SA 3.0
2012-04-03T05:37:02.563Z
2018-04-30T13:51:10.283Z
2018-04-30T13:51:10.283Z
Lev Reyzin
<p>Dana Angluin (<a href="http://www.sciencedirect.com/science/article/pii/0890540187900526" rel="noreferrer">1987</a>; <a href="http://www.cse.iitk.ac.in/users/chitti/thesis/references/learningRegSetsFromQueriesAndCounterExamples.pdf" rel="noreferrer">pdf</a>) defines a learning model with membership queries and theory queries (counterexamples to a proposed function). She shows that a regular language that is represented by a minimal DFA of <span class="math-container">$n$</span> states is learnable in polynomial time (where the proposed functions are DFAs) with <span class="math-container">$O(mn^2)$</span> membership-queries and at most <span class="math-container">$n−1$</span> theory-queries (<span class="math-container">$m$</span> is the size of the largest counter-example provided by the tutor). Unfortunately, she does not discuss lower bounds.</p>
<p>We can generalize the model slightly by assuming a magical tutor that can check equality between arbitrary functions and provide counterexamples if different. Then we can ask how hard it is to learn classes bigger than regular languages. I am interested in this generalization and the original restriction to regular languages.</p>
<p><strong>Are there any known lower bounds on the number of queries in the membership and counterexample model?</strong></p>
<p>I am interested in lower bounds on the number of membership queries, theory queries, or trade-offs between the two. I am interested in lower-bounds for any class of functions, even for more complicated classes than regular languages.</p>
<p>If there are no lower-bounds: <strong>Are there known bariers to proving query lower bounds in this model?</strong></p>
<hr />
<h3>Related questions</h3>
<p><a href="https://cs.stackexchange.com/q/118/55">Are there improvements on Dana Angluin's algorithm for learning regular sets</a></p>

<cc.complexity-theory><machine-learning><lower-bounds><lg.learning><query-complexity>
Lower bounds for learning in the membership query and counterexample model
Artem Kaznatcheev
# Lower bounds for learning in the membership query and counterexample model

(Asked by: username_0 on 2012-04-03)

Dana Angluin ([1987](http://www.sciencedirect.com/science/article/pii/0890540187900526); [pdf](http://www.cse.iitk.ac.in/users/chitti/thesis/references/learningRegSetsFromQueriesAndCounterExamples.pdf)) defines a learning model with membership queries and theory queries (counterexamples to a proposed function). She shows that a regular language that is represented by a minimal DFA of $n$ states is learnable in polynomial time (where the proposed functions are DFAs) with $O(mn^2)$ membership-queries and at most $n−1$ theory-queries ($m$ is the size of the largest counter-example provided by the tutor). Unfortunately, she does not discuss lower bounds.

We can generalize the model slightly by assuming a magical tutor that can check equality between arbitrary functions and provide counterexamples if different. Then we can ask how hard it is to learn classes bigger than regular languages. I am interested in this generalization and the original restriction to regular languages.

**Are there any known lower bounds on the number of queries in the membership and counterexample model?**

I am interested in lower bounds on the number of membership queries, theory queries, or trade-offs between the two. I am interested in lower-bounds for any class of functions, even for more complicated classes than regular languages.

If there are no lower-bounds: **Are there known bariers to proving query lower bounds in this model?**

---

### Related questions

[Are there improvements on Dana Angluin's algorithm for learning regular sets](https://cs.stackexchange.com/q/118/55)

**Tags:** cc.complexity-theory, machine-learning, lower-bounds, lg.learning, query-complexity


---

## 1 answers

### Answer by username_1 on 2012-04-03. Score: 11 | Accepted answer

Yes, some lower bounds are known. For example, assuming $NP \neq coNP$, you cannot even properly learn read-thrice DNF formulas in polynomial time. There is a whole [paper](http://dl.acm.org/citation.cfm?id=296694) developing such hardness results using something called the "representation problem".

To answer your linked-to question: Schapire, in his [dissertation](http://dl.acm.org/citation.cfm?id=136314), in addition to proving that "weak learning" = "strong learning," also improved on Angluin's bound and gave an algorithm that uses $O(n)$ equivalence queries and $O(n^2+ n \log m)$ membership queries for learning DFA.

One easy way to get lower bounds is information-theory. You can figure out how many distinct targets there are and how many bits a query gives you, etc. These upper bounds come close but aren't there. There are also issues one needs to think about regarding how the "counterexamples" arrive to the learner. A well-chosen counterexample can give away quite a lot of information.

*Update to the discussion above*: Angluin and Dohrn address the question learning with random counterexamples in a [recent paper](http://proceedings.mlr.press/v76/angluin17a/angluin17a.pdf).

> **Comments:**
> **username_0**: Thanks for the answer! Do you mind if I give your answer to my linked question on the linked question (with links back here)? Or do you plan to make a CS.SE account? I totally agree with paragraph 3, I was fooling around with demanding that the tutor give a minimal counterexample and learning seems to become much easier.  
> **username_1**: No problem! And feel free to post to the linked CS.SE question.  
> **username_0**: I read through the relevant part of Schapire's thesis (section 5.4.5) and [summarized the improvement](http://cs.stackexchange.com/a/1021/55), hopefully I got the gist right. I will look more closely at the lower-bounds paper you cite later in the week :D.  
> **username_1**: Cool. I'd upvote it if I had a CS.SE account :)  

---

