TY - JOUR
T1 - On the importance of small coordinate projections
AU - Mendelson, Shahar
AU - Philips, Petra
N1 - Publisher Copyright:
© 2004 Shahar Mendelson and Petra Philips.
PY - 2004/3/1
Y1 - 2004/3/1
N2 - It has been recently shown that sharp generalization bounds can be obtained when the function class from which the algorithm chooses its hypotheses is "small" in the sense that the Rademacher averages of this function class are small. We show that a new more general principle 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. As an example, we prove that this geometric property of the function class is exactly the reason why the two lately proposed frameworks, the luckiness (Shawe-Taylor et al., 1998) and the algorithmic luckiness (Herbrich and Williamson, 2002), can be used to establish generalization bounds.
AB - It has been recently shown that sharp generalization bounds can be obtained when the function class from which the algorithm chooses its hypotheses is "small" in the sense that the Rademacher averages of this function class are small. We show that a new more general principle 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. As an example, we prove that this geometric property of the function class is exactly the reason why the two lately proposed frameworks, the luckiness (Shawe-Taylor et al., 1998) and the algorithmic luckiness (Herbrich and Williamson, 2002), can be used to establish generalization bounds.
KW - Coordinate projections
KW - Data-dependent complexities
KW - Generalization bounds
KW - Statistical learning theory
UR - http://www.scopus.com/inward/record.url?scp=84897541071&partnerID=8YFLogxK
M3 - Article
SN - 1532-4435
VL - 5
SP - 219
EP - 238
JO - Journal of Machine Learning Research
JF - Journal of Machine Learning Research
ER -