Random Subclass Bounds
It has been recently shown that sharp generalization bounds can be obtained when the function class from which the algorithm choo-ses its hypotheses is “small” in the sense that the Rademacher averages of this function class are small [8,9]. Seemingly based on different arguments, generalization bounds were obtained in the compression scheme [7], luckiness [13], and algorithmic luckiness [6] frameworks in which the “size” of the function class is not specified a priori.