# Support Vector Machines with the Hard-Margin Loss: Optimal Training via Combinatorial Benders' Cuts

arXiv: https://arxiv.org/abs/2207.07690 · HTML: https://mlsanity.com/paper/2207.07690/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 63 references that are in the map.
- First posted on arXiv 15 Jul 2022.

## Builds on (most cited first, 8 of 8)

- [Born-Again Tree Ensembles](https://mlsanity.com/paper/2003.11132/) (2020)
- [Optimal Counterfactual Explanations in Tree Ensembles](https://mlsanity.com/paper/2106.06631/) (2021)
- [Lossless Compression of Deep Neural Networks](https://mlsanity.com/paper/2001.00218/) (2020)
- [Optimization Problems for Machine Learning: A Survey](https://mlsanity.com/paper/1901.05331/) (2019)
- [HG-means: A scalable hybrid genetic algorithm for minimum sum-of-squares clustering](https://mlsanity.com/paper/1804.09813/) (2018)
- [Optimal Decision Diagrams for Classification](https://mlsanity.com/paper/2205.14500/) (2022)
- [Mixed Integer Linear Programming for Feature Selection in Support Vector Machine](https://mlsanity.com/paper/1808.02435/) (2018)
- [Separable Convex Optimization with Nested Lower and Upper Constraints](https://mlsanity.com/paper/1703.01484/) (2017)

## Built on by (most cited first, 2 of 2)

- [Learning to control inexact Benders decomposition via reinforcement learning](https://mlsanity.com/paper/2508.06700/) (2025)
- [A Mathematical Optimization Approach to Multisphere Support Vector Data Description](https://mlsanity.com/paper/2507.11106/) (2025)

## Abstract (arXiv)

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, since 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 to converge much more quickly towards a global optimum. Through extensive numerical analyses on classical benchmark data sets, our solution algorithm solves, for the first time, 117 new data sets to optimality and achieves a reduction of 50% in the average optimality gap for the hardest datasets of the benchmark.