Data-dependent Generalization Bounds for Multi-class Classification

Abstract

In this paper, we study data-dependent generalization error bounds exhibiting a mild dependency on the number of classes, making them suitable for multi-class learning with a large number of label classes. The bounds generally hold for empirical multi-class risk minimization algorithms using an arbitrary norm as regularizer. Key to our analysis are new structural results for multi-class Gaussian complexities and empirical ${\ell }_{\infty }$-norm covering numbers, which exploit the Lipschitz continuity of the loss function with respect to the ${\ell }_2$- and ${\ell }_{\infty }$-norm, respectively. We establish data-dependent error bounds in terms of complexities of a linear function class defined on a finite set induced by training examples, for which we show tight lower and upper bounds. We apply the results to several prominent multi-class learning machines, exhibiting a tighter dependency on the number of classes than the state of the art. For instance, for the multi-class SVM by Crammer and Singer (2002), we obtain a data-dependent bound with a logarithmic dependency which significantly improves the previous square-root dependency. Experimental results are reported to verify the effectiveness of our theoretical findings.

References in corpus (8)

• Large-scale Multi-label Learning with Missing Labels
• LSHTC: A Benchmark for Large-Scale Text Classification
• Conditional Probability Tree Estimation Analysis and Algorithms
• Multiclass learnability and the ERM principle
• Structured Prediction Theory Based on Factor Graph Complexity
• Efficient Large Scale Video Classification
• Distributed Optimization of Multi-Class SVMs
• Generalization error bounds for learning to rank: Does the length of document lists matter?