Support vector machines with the hard-margin loss: optimal training via combinatorial Benders’ cuts

The classical hinge-loss support vector machines (SVMs) model is sensitive to outlier observations due to the unboundedness of its loss function. To circumvent this issue, recent studies have focused on non-convex loss functions, such as the hard-margin loss, which associates a constant penalty to any misclassified or within-margin sample. Applying this loss function yields much-needed robustness for critical applications, but it also leads to an NP-hard model that makes training difficult: current exact optimization algorithms show limited scalability, whereas heuristics are not able to find high-quality solutions consistently. Against this background, we propose new integer programming strategies that significantly improve our ability to train the hard-margin SVM model to global optimality. We introduce an iterative sampling and decomposition approach, in which smaller subproblems are used to separate combinatorial Benders’ cuts. Those cuts, used within a branch-and-cut algorithm, permit our solution framework to converge much more quickly toward a global optimum. Through extensive numerical analyses on classical benchmark data sets, our solution algorithm solves, for the first time, 117 new data sets out of 873 to optimality and achieves a reduction of 50% in the average optimality gap for the hardest datasets of the benchmark.