On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels
This addresses the generalization behavior of over-parametrized models like neural networks, offering insights into non-monotonic risk patterns, though it is incremental as it builds on existing kernel and interpolation theories.
The paper investigates the risk behavior of minimum-norm interpolants in Reproducing Kernel Hilbert Spaces, showing it follows a multiple-descent pattern with non-monotonic changes as sample size increases, supported by empirical evidence matching theoretical predictions. It also provides new guarantees for over-parametrized neural networks by linking them to these interpolants.
We study the risk of minimum-norm interpolants of data in Reproducing Kernel Hilbert Spaces. Our upper bounds on the risk are of a multiple-descent shape for the various scalings of $d = n^α$, $α\in(0,1)$, for the input dimension $d$ and sample size $n$. Empirical evidence supports our finding that minimum-norm interpolants in RKHS can exhibit this unusual non-monotonicity in sample size; furthermore, locations of the peaks in our experiments match our theoretical predictions. Since gradient flow on appropriately initialized wide neural networks converges to a minimum-norm interpolant with respect to a certain kernel, our analysis also yields novel estimation and generalization guarantees for these over-parametrized models. At the heart of our analysis is a study of spectral properties of the random kernel matrix restricted to a filtration of eigen-spaces of the population covariance operator, and may be of independent interest.