Interpolating Classifiers Make Few Mistakes

Understand

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.