  In the framework of agnostic learning, one of the main open problems of the
theory of multi-category pattern classification is the characterization of the
way the complexity varies with the number C of categories. More precisely, if
the classifier is characterized only through minimal learnability hypotheses,
then the optimal dependency on C that an upper bound on the probability of
error should exhibit is unknown. We consider margin classifiers. They are based
on classes of vector-valued functions with one component function per category,
and the classes of component functions are uniform Glivenko-Cantelli classes.
For these classifiers, an L p-norm Sauer-Shelah lemma is established. It is
then used to derive guaranteed risks in the L $\infty$ and L 2-norms. These
bounds improve over the state-of-the-art ones with respect to their dependency
on C, which is sublinear.
