On the complexity of learning from counterexamples and membership queries

We show that for any concept class C the number of equiv-alence and membership queries that are needed to learn C is bounded from below by R(VC-dimension(C)). Fur-thermore we show that the required number of equivalence and membership queries is also bounded from below by R(LC- ARB(C) / log(1 + LC- ARB(C))), where LC- ARB(C) is the required number of steps in a differ-ent mo+l 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 on-line learning models and the related combinatorial parameters that have remained open (see section 3 of [MTl]). As an application of the first lower bound we determine the number of equivalence and membership queries that are needed to learn monomials of IC out of n variables. In the last section we examine learning algorithms for thresh-old gates that are based on equivalence queries. We show that a threshold gate can not only learn concepts but also non-decreasing functions in polynomially many steps. On the other hand we show that all distributed learning algo-rithms for threshold gates that are of a similar type as the A-rule or the WINNOW-algorithm are inherently slow