More Theorems about Scale-sensitive Dimensions and Learning

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 boundon the expected absolute error of this algorithm in terms of a scale-sensitive generalization of the Vapnik dimension proposed by Alon, Ben-David, Cesa-Bianchi and Haussler. We give lower bounds implying that our upper bounds cannot be improved by more than a constant in general. We apply this result, together with techniques due to Haussler, to obtain new upper bounds on packing numbers in terms of this scale-sensitive notion of dimension. Using a different technique, we obtain new bounds on packing numbers in terms of Kearns and Schapire's fat-shattering function. We show how to apply both packing bounds to obtain improved general bounds on the sample complexity of agnostic learning. For each epsilon > 0, we establish weaker sufficient and stronger necessary conditions for a class of [0, 1]-valued functions to be agnostical..