Computational complexity of linear large margin classification with ramp loss

TY - GEN

T1 - Computational complexity of linear large margin classification with ramp loss

AU - Maibing, Søren Frejstrup

AU - Igel, Christian

N1 - Conference code: 18

PY - 2015

Y1 - 2015

N2 - Minimizing the binary classification error with a linear model leads to an NP-hard problem. In practice, surrogate loss functions are used, in particular loss functions leading to large margin classification such as the hinge loss and the ramp loss. The intuitive large margin concept is theoretically supported by generalization bounds linking the expected classification error to the empirical margin error and the complexity of the considered hypotheses class. This article addresses the fundamental question about the computational complexity of determining whether there is a hypotheses class with a hypothesis such that the upper bound on the generalization error is below a certain value. Results of this type are important for model comparison and selection. This paper takes a first step and proves that minimizing a basic margin-bound is NP-hard when considering linear hypotheses and the p-margin loss function, which generalizes the ramp loss. This result directly implies the hardness of ramp loss minimization.

AB - Minimizing the binary classification error with a linear model leads to an NP-hard problem. In practice, surrogate loss functions are used, in particular loss functions leading to large margin classification such as the hinge loss and the ramp loss. The intuitive large margin concept is theoretically supported by generalization bounds linking the expected classification error to the empirical margin error and the complexity of the considered hypotheses class. This article addresses the fundamental question about the computational complexity of determining whether there is a hypotheses class with a hypothesis such that the upper bound on the generalization error is below a certain value. Results of this type are important for model comparison and selection. This paper takes a first step and proves that minimizing a basic margin-bound is NP-hard when considering linear hypotheses and the p-margin loss function, which generalizes the ramp loss. This result directly implies the hardness of ramp loss minimization.

M3 - Article in proceedings

T3 - JMLR: Workshop and Conference Proceedings

SP - 259

EP - 267

BT - Proceedings of the 18th International Conference on Artificial Intelligence and Statistics (AISTATS) 2015

A2 - Lebanon, Guy

A2 - Vishwanathan, S. V. N.

T2 - International Conference on Artificial Intelligence and Statistics 2015

Y2 - 9 May 2015 through 12 May 2015

ER -