On the proliferation of support vectors in high dimensions

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.

References in corpus (4)

• Classification vs regression in overparameterized regimes: Does the loss function matter?
• Understanding overfitting peaks in generalization error: Analytical risk curves for $l_2$ and $l_1$ penalized interpolation
• Near-Tight Margin-Based Generalization Bounds for Support Vector Machines
• Risk of the Least Squares Minimum Norm Estimator under the Spike Covariance Model

Cited by in corpus (5)

• Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures
• Error Scaling Laws for Kernel Classification under Source and Capacity Conditions
• When does gradient descent with logistic loss find interpolating two-layer networks?
• Minimax Supervised Clustering in the Anisotropic Gaussian Mixture Model: A new take on Robust Interpolation
• Depth Without the Magic: Inductive Bias of Natural Gradient Descent