On the proliferation of support vectors in high dimensions

Daniel Hsu, Vidya Muthukumar, Ji Xu
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:91-99, 2021.

Abstract

The support vector machine (SVM) is a well-established classification method whose name refers to the particular training examples, called support vectors, that determine the maximum margin separating hyperplane. The SVM classifier is known to enjoy good generalization properties when the number of support vectors is small compared to the number of training examples. However, recent research has shown that in sufficiently high-dimensional linear classification problems, the SVM can generalize well despite a proliferation of support vectors where all training examples are support vectors. In this paper, we identify new deterministic equivalences for this phenomenon of support vector proliferation, and use them to (1) substantially broaden the conditions under which the phenomenon occurs in high-dimensional settings, and (2) prove a nearly matching converse result.

Cite this Paper


BibTeX
@InProceedings{pmlr-v130-hsu21a, title = { On the proliferation of support vectors in high dimensions }, author = {Hsu, Daniel and Muthukumar, Vidya and Xu, Ji}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {91--99}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/hsu21a/hsu21a.pdf}, url = {https://proceedings.mlr.press/v130/hsu21a.html}, abstract = { The support vector machine (SVM) is a well-established classification method whose name refers to the particular training examples, called support vectors, that determine the maximum margin separating hyperplane. The SVM classifier is known to enjoy good generalization properties when the number of support vectors is small compared to the number of training examples. However, recent research has shown that in sufficiently high-dimensional linear classification problems, the SVM can generalize well despite a proliferation of support vectors where all training examples are support vectors. In this paper, we identify new deterministic equivalences for this phenomenon of support vector proliferation, and use them to (1) substantially broaden the conditions under which the phenomenon occurs in high-dimensional settings, and (2) prove a nearly matching converse result. } }
Endnote
%0 Conference Paper %T On the proliferation of support vectors in high dimensions %A Daniel Hsu %A Vidya Muthukumar %A Ji Xu %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-hsu21a %I PMLR %P 91--99 %U https://proceedings.mlr.press/v130/hsu21a.html %V 130 %X The support vector machine (SVM) is a well-established classification method whose name refers to the particular training examples, called support vectors, that determine the maximum margin separating hyperplane. The SVM classifier is known to enjoy good generalization properties when the number of support vectors is small compared to the number of training examples. However, recent research has shown that in sufficiently high-dimensional linear classification problems, the SVM can generalize well despite a proliferation of support vectors where all training examples are support vectors. In this paper, we identify new deterministic equivalences for this phenomenon of support vector proliferation, and use them to (1) substantially broaden the conditions under which the phenomenon occurs in high-dimensional settings, and (2) prove a nearly matching converse result.
APA
Hsu, D., Muthukumar, V. & Xu, J.. (2021). On the proliferation of support vectors in high dimensions . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:91-99 Available from https://proceedings.mlr.press/v130/hsu21a.html.

Related Material