Can equivalence queries be replaced by random examples in PAC learning?

Question

In exact learning models, algorithms often rely on equivalence queries (EQ) to verify hypotheses. In contrast, PAC learning uses only random labeled examples.

If a concept class is efficiently learnable using EQ queries, under what conditions can we simulate EQ using only random examples, and thus PAC-learn the same class?

• Are there general results connecting EQ-based learning to PAC learnability?

• What assumptions are needed on the concept class or hypothesis space?

• Are there known techniques to transform EQ-based learners into PAC learners?

Any references or examples would be of great help.

Answer 1

A concept class that has an efficient algorithm in the exact learning model with membership and equivalence queries also has an efficient algorithm in the PAC+MQ model, since equivalence queries can be efficiently simulated using random examples.

This was shown in a classic paper by Dana Angluin: Queries and Concept Learning. See also the recent survey: The Probably Approximately Correct Learning Model in Computational Learning Theory, Section 3.2.