Entropy Numbers of Linear Function Classes

摘要

This paper collects together a miscellany of results originally motivated by the analysis of the generalization performance of the "maximum-margin" algorithm due to Vapnik and others. The key feature of the paper is its operator-theoretic viewpoint. New bounds on covering numbers for classes related to Maximum Margin classes are derived directly without making use of a combinatorial dimension such as the VC-dimension. Specific contents of the paper include: 1. A new and self-contained proof of Maurey's theorem and some generalizations with small explicit values of constants; 2. Bounds on the covering numbers of maximum margin classes suitable for the analysis of their generalization performance; 3. The extension of such classes to those induced by balls in quasi-Banach spaces (such as l_p-norms with 0 < p <∞). 4. Extension of results on the covering numbers of convex hulls of basis functions to p-convex hulls (0 < p ≤ 1); 5. An appendix containing the tightest known bounds on the entropy numbers of the identity operator between l~n_(p1) and l~n_(p2) (0 < p_1 < p_2 ≤∞).