Søren Frejstrup Maibing

Computational Complexity of Linear Large Margin Classification With Ramp Loss

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 theoretical…