@techreport{Santana2022,
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, 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.},
archivePrefix = {arXiv},
arxivId = {2207.07690},
author = {Santana, {\'{I}}. and Serrano, B. and Schiffer, M. and Vidal, T.},
eprint = {2207.07690},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Santana et al/Santana et al. - 2022 - Support vector machines with the hard-margin loss Optimal training via combinatorial Benders' cuts.pdf:pdf},
institution = {arXiv:2207.07690},
title = {{Support vector machines with the hard-margin loss: Optimal training via combinatorial Benders' cuts}},
url = {https://arxiv.org/pdf/2207.07690.pdf},
year = {2022}
}

{"_id":"ppn6ZX3C9aYvkMDj6","bibbaseid":"santana-serrano-schiffer-vidal-supportvectormachineswiththehardmarginlossoptimaltrainingviacombinatorialbenderscuts-2022","author_short":["Santana, Ί.","Serrano, B.","Schiffer, M.","Vidal, T."],"bibdata":{"bibtype":"techreport","type":"techreport","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, 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.","archiveprefix":"arXiv","arxivid":"2207.07690","author":[{"propositions":[],"lastnames":["Santana"],"firstnames":["Ί."],"suffixes":[]},{"propositions":[],"lastnames":["Serrano"],"firstnames":["B."],"suffixes":[]},{"propositions":[],"lastnames":["Schiffer"],"firstnames":["M."],"suffixes":[]},{"propositions":[],"lastnames":["Vidal"],"firstnames":["T."],"suffixes":[]}],"eprint":"2207.07690","file":":C$\\$:/Users/Thibaut/Documents/Mendeley-Articles/Santana et al/Santana et al. - 2022 - Support vector machines with the hard-margin loss Optimal training via combinatorial Benders' cuts.pdf:pdf","institution":"arXiv:2207.07690","title":"Support vector machines with the hard-margin loss: Optimal training via combinatorial Benders' cuts","url":"https://arxiv.org/pdf/2207.07690.pdf","year":"2022","bibtex":"@techreport{Santana2022,\nabstract = {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.},\narchivePrefix = {arXiv},\narxivId = {2207.07690},\nauthor = {Santana, {\\'{I}}. and Serrano, B. and Schiffer, M. and Vidal, T.},\neprint = {2207.07690},\nfile = {:C$\\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Santana et al/Santana et al. - 2022 - Support vector machines with the hard-margin loss Optimal training via combinatorial Benders' cuts.pdf:pdf},\ninstitution = {arXiv:2207.07690},\ntitle = {{Support vector machines with the hard-margin loss: Optimal training via combinatorial Benders' cuts}},\nurl = {https://arxiv.org/pdf/2207.07690.pdf},\nyear = {2022}\n}\n","author_short":["Santana, Ί.","Serrano, B.","Schiffer, M.","Vidal, T."],"key":"Santana2022","id":"Santana2022","bibbaseid":"santana-serrano-schiffer-vidal-supportvectormachineswiththehardmarginlossoptimaltrainingviacombinatorialbenderscuts-2022","role":"author","urls":{"Paper":"https://arxiv.org/pdf/2207.07690.pdf"},"metadata":{"authorlinks":{}}},"bibtype":"techreport","biburl":"https://w1.cirrelt.ca/~vidalt/resources/My%20Collection.bib","dataSources":["yinfondEAJRbDM9sJ","sempRA6PhmAdGk3yG"],"keywords":[],"search_terms":["support","vector","machines","hard","margin","loss","optimal","training","via","combinatorial","benders","cuts","santana","serrano","schiffer","vidal"],"title":"Support vector machines with the hard-margin loss: Optimal training via combinatorial Benders' cuts","year":2022}