On the complexity of learning from counterexamples and membership queries

Abstract

It is shown that for any concept class C the number of equivalence and membership queries that are needed to learn C is bounded from below by Omega (VC-dimension(C)). Furthermore, it is shown that the required number of equivalence and membership queries is also bounded from below by Omega (LC-ARB(C)/log(1+LC-ARB(C))), where LC-ARB(C) is the required number of steps in a different model where no membership queries but equivalence queries with arbitrary subsets of the domain are permitted. These two relationships are the only relationships between the learning complexities of the common online learning models and the related combinatorial parameters that have remained open. As an application of the first lower bound, the number of equivalence and membership queries that are needed to learn monomials of k out of n variables is determined. Learning algorithms for threshold gates that are based on equivalence queries are examined. It is shown that a threshold gate can learn not only concepts but also nondecreasing functions in polynomially many steps.