Support Vector Machines with the Ramp Loss and the Hard Margin Loss
Abstract
In the interest of deriving classifiers that are robust to outlier observations, we present integer programming formulations of Vapnik's support vector machine (SVM) with the ramp loss and hard margin loss. The ramp loss allows a maximum error of 2 for each training observation, while the hard margin loss calculates error by counting the number of training observations that are in the margin or misclassified outside of the margin. SVM with these loss functions is shown to be a consistent estimator when used with certain kernel functions. In computational studies with simulated and real-world data, SVM with the robust loss functions ignores outlier observations effectively, providing an advantage over SVM with the traditional hinge loss when using the linear kernel. Despite the fact that training SVM with the robust loss functions requires the solution of a quadratic mixed-integer program (QMIP) and is NP-hard, while traditional SVM requires only the solution of a continuous quadratic program (QP), we are able to find good solutions and prove optimality for instances with up to 500 observations. Solution methods are presented for the new formulations that improve computational performance over industry-standard integer programming solvers alone.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Outliers can also be problematic for sampling and subgroup analysis.
“Outliers can also be problematic [46,222].”
From Fairness in machine learning: A survey (2024) · cites this paper as [46]
Cites
R: A Language and Environment for Statistical Computing
R Core Team (2000) · doi:10.32614/r.manuals · Cited by 355,706 · see citing works
Cortes, C., & Vapnik, V. (1995) · Machine Learning · doi:10.1007/bf00994018 · Cited by 59,421 · see citing works
Cortes, C., & Vapnik, V. N. (1995) · Machine Learning · doi:10.1023/a:1022627411411 · Cited by 34,565 · see citing works
Wu, Y., & Vapnik, V. N. (1999) · Technometrics · doi:10.2307/1271368 · Cited by 27,236 · see citing works
UCI Machine Learning Repository
Asuncion, A. (2007) · Medical Entomology and Zoology · Cited by 24,190 · see citing works
Seel, N. M. (2012) · Springer eBooks · doi:10.1007/978-1-4419-1428-6_5195 · Cited by 19,525 · see citing works
Russell, E. L., Chiang, L. H., & Braatz, R. D. (2000) · Advances in industrial control · doi:10.1007/978-1-4471-0409-4_3 · Cited by 7,938 · see citing works
Kernel Methods for Pattern Analysis
Shawe-Taylor, J. S., & Cristianini, N. (2004) · Cambridge University Press eBooks · doi:10.1017/cbo9780511809682 · Cited by 6,610 · see citing works
Advances in kernel methods: support vector learning
Schölkopf, B., Burges, C. J. C., & Smola, A. J. (1999) · doi:10.5555/299094 · Cited by 5,809 · see citing works
Integer and Combinatorial Optimization
Williams, H. P., Nemhauser, G. L., & Wolsey, L. A. (1990) · Journal of the Operational Research Society · doi:10.2307/2583737 · Cited by 5,526 · see citing works
Making Large-Scale SVM Learning PracticalPreprint
Joachims, T. (1998) · RePEc: Research Papers in Economics · doi:10.17877/de290r-14262 · Cited by 4,514 · see citing works
A Probabilistic Theory of Pattern Recognition
Devroye, L., Györfi, L., & Lugosi, G. (1996) · Stochastic Modelling and Applied Probability · doi:10.1007/978-1-4612-0711-5 · Cited by 3,274 · see citing works
Rademacher and Gaussian Complexities: Risk Bounds and Structural Results
Bartlett, P. L., & Mendelson, S. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44581-1_15 · Cited by 1,989 · see citing works
On the method of bounded differences
McDiarmid, C. (1989) · Cambridge University Press eBooks · doi:10.1017/cbo9781107359949.008 · Cited by 1,450 · see citing works
Zaki, M. J., & Meira, W. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108564175.026 · Cited by 1,437 · see citing works
Integer and combinatorial optimization
Karla L. Hoffman, E. A. (1999) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(99)91259-2 · Cited by 1,132 · see citing works
Arcing classifier (with discussion and a rejoinder by the author)
Breiman, L. (1998) · The Annals of Statistics · doi:10.1214/aos/1024691079 · Cited by 1,104 · see citing works
Semi-Supervised Support Vector Machines
Bennett, K. P., & Demiriz, A. (1998) · Cited by 832 · see citing works
Cancer Diagnosis Via Linear Programming
Mangasarian, O. L., & Wolberg, W. H. (1990) · Minds at UW (University of Wisconsin) · Cited by 668 · see citing works
Optimization Techniques for Semi-Supervised Support Vector Machines
Chapelle, O., Sindhwani, V., & Keerthi, S. S. (2008) · MPG.PuRe (Max Planck Society) · doi:10.5555/1390681.1390688 · Cited by 408 · see citing works
de Tejada, J. G. S., & Seijas, J. (2007) · Springer eBooks · doi:10.1007/0-387-37452-3_7 · Cited by 380 · see citing works
randomForest: Breiman and Cutlers Random Forests for Classification and Regression
Breiman, L., Cutler, A., Liaw, A. I., & Wiener, M. C. (2002) · doi:10.32614/cran.package.randomforest · Cited by 370 · see citing works
Trading convexity for scalability
Collobert, R., Sinz, F. H., Weston, J., & Bottou, L. (2006) · International Conference on Machine Learning · doi:10.1145/1143844.1143870 · Cited by 369 · see citing works
Linear and Nonlinear Separation of Patterns by Linear Programming
Mangasarian, O. L. (1965) · Operations Research · doi:10.1287/opre.13.3.444 · Cited by 330 · see citing works
Consistency of Support Vector Machines and Other Regularized Kernel Classifiers
Steinwart, I. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.839514 · Cited by 226 · see citing works
Shen, X. T., Tseng, G. C., Zhang, X., et al. (2003) · Journal of the American Statistical Association · doi:10.1198/016214503000000639 · Cited by 193 · see citing works
Support Vector Machines are Universally Consistent
Steinwart, I. (2002) · Journal of Complexity · doi:10.1006/jcom.2002.0642 · Cited by 163 · see citing works
The densest hemisphere problem
Johnson, D. S., & Preparata, F. P. (1978) · Theoretical Computer Science · doi:10.1016/0304-3975(78)90006-3 · Cited by 152 · see citing works
Multisurface method of pattern separation
Mangasarian, O. L. (1968) · IEEE Transactions on Information Theory · doi:10.1109/tit.1968.1054229 · Cited by 148 · see citing works
Robust support vector machine training via convex outlier ablation
Xu, L., Crammer, K., & Schuurmans, D. (2006) · Cited by 147 · see citing works
Minimizing Misclassifications in Linear Discriminant Analysis*
Kœhler, G. J., & Erengüç, Ş. S. (1990) · Decision Sciences · doi:10.1111/j.1540-5915.1990.tb00317.x · Cited by 140 · see citing works
Classification and Regression via Integer Optimization
Bertsimas, D., & Shioda, R. (2007) · Operations Research · doi:10.1287/opre.1060.0360 · Cited by 116 · see citing works
On Robustness Properties of Convex Risk Minimization Methods for Pattern RecognitionPreprint
Christmann, A., & Steinwart, I. (2003) · RePEc: Research Papers in Economics · doi:10.17877/de290r-15035 · Cited by 113 · see citing works
Multicategory ψ-Learning and Support Vector Machine: Computational Tools
Liu, Y., Shen, X. T., & Doss, H. (2005) · Journal of Computational and Graphical Statistics · doi:10.1198/106186005x37238 · Cited by 108 · see citing works
Empirical risk minimization for support vector classifiers
Pérez‐Cruz, F., Navia-Vázquez, A., Figueiras-Vidal, A. R., & Artés-Rodrı́guez, A. (2003) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2003.809399 · Cited by 49 · see citing works
Hybrid misclassification minimization
Chen, C., & Mangasarian, O. L. (1996) · Advances in Computational Mathematics · doi:10.1007/bf02124738 · Cited by 47 · see citing works
Brooks, J. P., & Lee, E. K. (2008) · Annals of Operations Research · doi:10.1007/s10479-008-0424-0 · Cited by 44 · see citing works
Self-citationMultivariate classification trees based on minimum features discrete support vector machines
Orsenigo, C. (2003) · IMA Journal of Management Mathematics · doi:10.1093/imaman/14.3.221 · Cited by 39 · see citing works
Constrained discriminant analysis via 0/1 mixed integer programming
Gallagher, R. J., Lee, E. K., & Patterson, D. A. (1997) · Annals of Operations Research · doi:10.1023/a:1018943025993 · Cited by 36 · see citing works
Surveys in combinatorics, 1989
Siemons, J. (1989) · Cambridge University Press eBooks · Cited by 31 · see citing works
Evaluating Membership Functions for Fuzzy Discrete SVM
Orsenigo, C., & Vercellis, C. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-73400-0_23 · Cited by 5 · see citing works
Softening the Margin in Discrete SVM
Orsenigo, C., & Vercellis, C. (2007) · Springer eBooks · doi:10.1007/978-3-540-73435-2_5 · Cited by 4 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Generalized Cross Entropy Loss for Training Deep Neural Networks with Noisy Labels
Zhang, Z., & Sabuncu, M. R. (2018) · arXiv · doi:10.48550/arxiv.1805.07836 · Cited by 1,907 · see citing works
Fairness in machine learning: A survey
Caton, S., & Haas, C. (2024) · ACM Computing Surveys · doi:10.1145/3616865 · Cited by 646 · see citing works
Fairness in Machine Learning: A Survey
Caton, S., & Haas, C. (2020) · arXiv · doi:10.48550/arxiv.2010.04053 · Cited by 646 · see citing works
Quantum computing and supervised machine learning
Oneto, L., Ridella, S., & Anguita, D. (2017) · Quantum Inspired Computational Intelligence · doi:10.1016/b978-0-12-804409-4.00002-4 · Cited by 11 · see citing works
- Authors
- Brooks, J. P.
- Affiliations
- Virginia Commonwealth University (US)
- Corresponding author
- Brooks, J. Paul
- ORCID
- Brooks, J. Paul
- Venue
- Operations Research
- Published
- 2011-04
- Volume
- 59
- Issue
- 2
- Pages
- 467-479
- ISSN
- 0030-364X (ISSN-L)
- 1526-5463
- OpenAlex
- W2032708784
- Cited by
- 145
- References
- 42
- Citations by year
- 2026: 5 · 2025: 15 · 2024: 14 · 2023: 10 · 2022: 16 · 2021: 16 · 2020: 13 · 2019: 9 · 2018: 9 · 2017: 5 · 2016: 6 · 2015: 12 · 2014: 7 · 2013: 4 · 2012: 3
- FWCI
- 4.42
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Operations Research (publishedVersion)
- Funders
- National Aeronautics and Space Administration
- Virginia Commonwealth University
- National Institutes of Health
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Data Classification
- Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
- Social Sciences › Decision Sciences › Management Science and Operations Research › Risk and Portfolio Optimization
- Keywords
- support vector machine, ramp loss, robust classification, outlier robustness, integer programming formulation, hinge loss, kernel methods, estimator consistency, NP-hardness
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
