PREDICTION, LEARNING, UNIFORM-CONVERGENCE, AND SCALE-SENSITIVE DIMENSIONS

We present a new general-purpose algorithm for learning classes of [0, 1] -valued functions in a generalization of the prediction model and prove a general upper bound on the expected absolute error of this alg orithm in terms of a scale-sensitive generalization of the Vapnik dime nsion proposed by Alon, Ben-David, Cesa-Bianchi, and Haussler. We give lower bounds implying that our upper bounds cannot be improved by mor e than a constant factor in general. We apply this result, together wi th techniques due to Haussler and to Benedek and Itai, to obtain new u pper bounds on packing numbers in terms of this scale-sensitive notion of dimension. Using a different technique, we obtain new bounds on pa cking numbers in terms of Kearns and Schapire's fat-shattering functio n. We show how to apply both packing bounds to obtain improved general bounds on the sample complexity of agnostic learning. For each epsilo n > 0, we establish weaker sufficient and stronger necessary condition s for a class of [0, 1] -valued functions to be agnostically learnable to within epsilon and to be an E-uniform Glivenko-Cantelli class. (C) Academic Press.