This paper provides elementary analyses of the regret and generalization of minimum-norm interpolating classifiers (MNIC). The MNIC is the function of smallest Reproducing Kernel Hilbert Space norm that perfectly interpolates a label pattern on a finite data set. We derive a mistake bound for MNIC and a regularized variant that holds for all data sets. This bound follows from elementary properties of matrix inverses. Under the assumption that the data is independently and identically distributed, the mistake bound implies 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 matches similar rates derived for margin classifiers and perceptrons. We derive several plausible generative models where the norm of the interpolating classifier is bounded or grows at a rate sublinear in $n$. We also show that as long as the population class conditional distributions are sufficiently separable in total variation, then MNIC generalizes with a fast rate.

本文分析了最小范数插值分类器的遗憾和概括，并推导出一种适用于所有数据集的错误边界和正则化变量。当数据独立同分布时，错误边界意味着 MNIC 的泛化率与插值解的范数成比例，与数据点数成反比。作者提出了几个合理的生成模型，并证明只要总变差足够可分，MNIC就可以以快速率进行泛化。

插值分类器几乎不犯错