General bounds on the number of examples needed for learning probabilistic concepts

Given a p-concept class C, we define two important functions d(c)(gamma), d(c)'(gamma) (related to the notion of gamma-shattering). We prove a lower bound of Omega((d(c)(gamma)-1)/(epsilon gamma 2)) on the number of examples required for learning C with an (epsilon,gamma)-good model of probability. We prove similar lower bounds for some other learning models like learning with gamma-bounded absolute (or quadratic) difference or]earning with a gamma-good decision rule, For the class ND of nondecreasing p-concepts on the real domain, d(ND)(gamma) = Omega(1/gamma) It can be shown that the resulting lower bounds for learning ND (within the models in consideration) are tight to within a logarithmic factor. In order to get the ''almost-matching'' upper bounds, we introduce a new method for designing learning algorithms: dynamic partitioning of the domain by use of splitting trees. The paper also contains a discussion of the gaps between the general lower bounds and the corresponding general upper bounds, It can be shown that, under very mild conditions, these gaps are quite narrow. (C) 1996 Academic Press, Inc.