Characterization of data complexity for SVM methods

This paper provides new characterization of data complexity for margin-based methods also known as SVMs, kernel methods etc. Under the predictive learning setting, the complexity of a given data set is directly related to model complexity, i.e. the flexibility of a set of admissible models used to describe this data. There are two distinct approaches to model complexity control: traditional model-based where complexity is controlled via parameterization of admissible models, and margin-based where complexity is controlled by the size of margin (in a specially designed empirical loss function). This paper emphasizes the role of margin for complexity control, and proposes a simple index for data complexity suitable for classification and regression problems.