Interpolating Classifiers with Few Mistakes
Tengyuan Liang and Benjamin Recht; 24(20):1−27, 2023.
Abstract
This paper presents a basic analysis of the regret and generalization capabilities of minimum-norm interpolating classifiers (MNIC). MNIC is a function that perfectly interpolates a label pattern on a finite dataset and has the smallest norm in the Reproducing Kernel Hilbert Space. We establish a bound on the number of mistakes made by MNIC, as well as a regularized variant that applies to all datasets. This bound is derived using fundamental properties of matrix inverses. Assuming that the data is independently and identically distributed, the mistake bound indicates that MNIC generalizes at a rate proportional to the norm of the interpolating solution and inversely proportional to the number of data points. This rate is consistent with rates obtained for margin classifiers and perceptrons. We also propose several plausible generative models where the norm of the interpolating classifier is either bounded or grows at a sublinear rate with respect to the number of data points. Additionally, we demonstrate that as long as the population class conditional distributions are sufficiently separable in total variation, MNIC generalizes with a fast rate.
[abs]