New Equivalences Between Interpolation and SVMs: Kernels and Structured Features
This work addresses a theoretical gap in machine learning by providing more flexible conditions for connecting SVMs to interpolation, which is incremental as it extends prior analyses to less restrictive scenarios.
The paper tackles the problem of understanding when support vector machines (SVMs) behave like minimum-norm interpolants by developing a new analysis framework that relaxes restrictive assumptions on data distributions and feature spectra, showing that support vector proliferation occurs in broader settings like bounded orthonormal and sub-Gaussian features, and uses this to prove novel generalization results for kernel SVM classification.
The support vector machine (SVM) is a supervised learning algorithm that finds a maximum-margin linear classifier, often after mapping the data to a high-dimensional feature space via the kernel trick. Recent work has demonstrated that in certain sufficiently overparameterized settings, the SVM decision function coincides exactly with the minimum-norm label interpolant. This phenomenon of support vector proliferation (SVP) is especially interesting because it allows us to understand SVM performance by leveraging recent analyses of harmless interpolation in linear and kernel models. However, previous work on SVP has made restrictive assumptions on the data/feature distribution and spectrum. In this paper, we present a new and flexible analysis framework for proving SVP in an arbitrary reproducing kernel Hilbert space with a flexible class of generative models for the labels. We present conditions for SVP for features in the families of general bounded orthonormal systems (e.g. Fourier features) and independent sub-Gaussian features. In both cases, we show that SVP occurs in many interesting settings not covered by prior work, and we leverage these results to prove novel generalization results for kernel SVM classification.