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

Download:

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.

Citation

Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. 2020. “On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels.” Conference on Learning Theory, pmlr 125: 2683-2711, 2020.

@InProceedings{Liang_2020,
  title = 	 {On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels},
  author =       {Liang, Tengyuan and Rakhlin, Alexander and Zhai, Xiyu},
  booktitle = 	 {Proceedings of Thirty Third Conference on Learning Theory},
  pages = 	 {2683--2711},
  year = 	 {2020},
  editor = 	 {Abernethy, Jacob and Agarwal, Shivani},
  volume = 	 {125},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {09--12 Jul},
  publisher =    {PMLR}
}