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

Ítalo Santana (), Breno Serrano (), Maximilian Schiffer () and Thibaut Vidal ()
Additional contact information
Ítalo Santana: Pontifical Catholic University of Rio de Janeiro
Breno Serrano: Technical University of Munich
Maximilian Schiffer: Technical University of Munich
Thibaut Vidal: Polytechnique Montréal

Journal of Global Optimization, 2025, vol. 92, issue 1, No 9, 205-225

Abstract: Abstract 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.

Keywords: Combinatorial optimization; Support vector machines; Hard margin loss; Combinatorial Benders’ cuts; Sampling strategies (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-025-01483-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:92:y:2025:i:1:d:10.1007_s10898-025-01483-8

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-025-01483-8

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().