Sample Complexity Result for Multi-category Classifiers of Bounded Variation

In the VC framework[42], both for binary and multi-category classification tasks, when minimal assumption on the predictive model is made, the (optimal) way one controls the uniform convergence of the empirical performance to the generalization one depends on the loss function used based on which these performances are defined. The choice of the loss function leads to an upper bound involving one of capacity measures, the quantity characterizing the rate of the uniform convergence. The seminal work dealt with the standard indicator loss function [43] leading to bounds involving the VC-dimension as a capacity measure. This was improved in [12] via the Rademacher complexity since the mentioned capacity measure is upper bounded by the VC-dimension. Classifiers implementing real-valued functions offer a richer setting to the assessment of their classification performance since the latter can be defined based on a family of margin loss functions which can be distinguished into two classes: margin indicator loss function and those that are Lipschitz continuous [27].