Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon

Alexander Rakhlin, Xiyu Zhai
Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:2595-2623, 2019.

Abstract

We show that minimum-norm interpolation in the Reproducing Kernel Hilbert Space corresponding to the Laplace kernel is not consistent if input dimension is constant. The lower bound holds for any choice of kernel bandwidth, even if selected based on data. The result supports the empirical observation that minimum-norm interpolation (that is, exact fit to training data) in RKHS generalizes well for some high-dimensional datasets, but not for low-dimensional ones.

Cite this Paper

BibTeX
@InProceedings{pmlr-v99-rakhlin19a, title = {Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon}, author = {Rakhlin, Alexander and Zhai, Xiyu}, booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory}, pages = {2595--2623}, year = {2019}, editor = {Beygelzimer, Alina and Hsu, Daniel}, volume = {99}, series = {Proceedings of Machine Learning Research}, month = {25--28 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v99/rakhlin19a/rakhlin19a.pdf}, url = {https://proceedings.mlr.press/v99/rakhlin19a.html}, abstract = { We show that minimum-norm interpolation in the Reproducing Kernel Hilbert Space corresponding to the Laplace kernel is not consistent if input dimension is constant. The lower bound holds for any choice of kernel bandwidth, even if selected based on data. The result supports the empirical observation that minimum-norm interpolation (that is, exact fit to training data) in RKHS generalizes well for some high-dimensional datasets, but not for low-dimensional ones.} }
Endnote
%0 Conference Paper %T Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon %A Alexander Rakhlin %A Xiyu Zhai %B Proceedings of the Thirty-Second Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2019 %E Alina Beygelzimer %E Daniel Hsu %F pmlr-v99-rakhlin19a %I PMLR %P 2595--2623 %U https://proceedings.mlr.press/v99/rakhlin19a.html %V 99 %X We show that minimum-norm interpolation in the Reproducing Kernel Hilbert Space corresponding to the Laplace kernel is not consistent if input dimension is constant. The lower bound holds for any choice of kernel bandwidth, even if selected based on data. The result supports the empirical observation that minimum-norm interpolation (that is, exact fit to training data) in RKHS generalizes well for some high-dimensional datasets, but not for low-dimensional ones.
APA
Rakhlin, A. & Zhai, X.. (2019). Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon. Proceedings of the Thirty-Second Conference on Learning Theory, in Proceedings of Machine Learning Research 99:2595-2623 Available from https://proceedings.mlr.press/v99/rakhlin19a.html.

Related Material