ON THE SAMPLE COMPLEXITY OF CONSISTENT LEARNING WITH ONE-SIDED ERROR

Although consistent learning is sufficient for PAC-learning, it has no t been found what strategy makes learning more efficient, especially o n the sample complexity, i.e., the number of examples required. For th e first step towards this problem, classes that have consistent learni ng algorithms with one-sided error are considered. A combinatorial qua ntity called maximal particle sets is introduced, and an upper bound o f the sample complexity of consistent learning with one-sided error is obtained in terms of maximal particle sets. For the class of n-dimens ional axis-parallel rectangles, one of those classes that are consiste ntly learnable with one-sided error, the cardinality of the maximal pa rticle set is estimated and O(d/epsilon + 1/epsilon log 1/delta) upper bound of the learning algorithm for the class is obtained. This bound improves the bounds due to Blumer et al. [2] and meets the lower boun d within a constant Factor.