On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels

Abstract

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^{\alpha }$, $\alpha \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.

References in corpus (8)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Benign Overfitting in Linear Regression
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate
• To understand deep learning we need to understand kernel learning
• Does data interpolation contradict statistical optimality?
• Learning without Concentration

Cited by in corpus (4)

• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-${\ell }_1$-Norm Interpolated Classifiers
• Training Neural Networks as Learning Data-adaptive Kernels: Provable Representation and Approximation Benefits
• On the Universality of the Double Descent Peak in Ridgeless Regression
• Deep Networks Provably Classify Data on Curves