Separating distribution-free and mistake-bound learning models overthe Boolean domain

摘要

Two of the most commonly used models in computational learningtheory are the distribution-free model, in which examples are chosenfrom a fixed but arbitrary distribution, and the absolute mistake-boundmodel, in which examples are presented in order by an adversary. Overthe Boolean domain {0,1}n, it is known that if the learner isallowed unlimited computational resources, then any concept classlearnable in one model is also learnable in the other. In addition, anypolynomial-time learning algorithm for a concept class in themistake-bound model can be transformed into one that learns the class inthe distribution-free model. It is shown that if one-way functionsexist, then the converse does not hold. The author presents a conceptclass over {0.1}n that is learnable in the distribution-freemodel but is not learnable in the absolute mistake-bound model ifone-way functions exist. In addition, the concept class remains hard tolearn in the mistake-bound model, even if the learner is allowed apolynomial number of membership queries