Rademacher Complexity and Generalization Performance of Multi-category Margin Classifiers

Although the theory of binary pattern classification is well established [1, 2], the theory of multicategory classificationis far from being complete. The research in this case addresses problems such as the sample-complexity analysis of empirical risk minimization algorithms[3], or consistency analysis of multi-class loss functions and of specific families of classifiers [4]. Another open question is the optimal dependency of guaranteed risks of multi-category classifiers on the number C of categories and the sample size m. It is all the more the case for the problems that involve a large number of classes. When the considered classifiers are margin ones that take decision based on a score per category, the dependency on the margin parameter γ also becomes relevant to the characterization of their generalization performance. If this question has been mainly studied for specific families of classifiers, be it k-nearest neighbors [5], kernel methods [6, 7] and decision trees [8], tackling it under minimal learnability assumptions remains a challenging task. This paper focuses on obtaining guaranteed risks under such assumptions.