Lower bounds for learning in the membership query and counterexample model

Question

Dana Angluin (1987; 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

Answer 1

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 developing such hardness results using something called the "representation problem".

To answer your linked-to question: Schapire, in his dissertation, 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.

• Artem Kaznatcheev: 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.
• Lev Reyzin: No problem! And feel free to post to the linked CS.SE question.
• Artem Kaznatcheev: I read through the relevant part of Schapire's thesis (section 5.4.5) and summarized the improvement, hopefully I got the gist right. I will look more closely at the lower-bounds paper you cite later in the week :D.
• Lev Reyzin: Cool. I'd upvote it if I had a CS.SE account :)