On the Importance of Small Coordinate Projections
Shahar Mendelson, Petra Philips · ANU Open Research (Australian National University) · 2004
It has been recently shown that sharp generalization bounds can be obtained when the function class from which the algorithm choses its hypotheses is \\small" in the sense that the Rademacher averages of this function class are small. We show that a new more general priciple guarantees good generalization bounds. The new principle requires that random coordinate projections of the function class evaluated on random samples are \\small" with high probability and that the random class of functions allows symmetrization. We prove that this geometric property of the function class is exactly the reason why the two lately proposed frameworks, the luckiness [14] and the algorithmic luckiness [5], can be used to establish generalization bounds. Furthermore, we investigate the connection of this property to the notion of stability of learning algorithms [4]. 1.