conftrace_

2019 COLT COLT 2019

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

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.

🐣 Hot Topic Early Bird - generalization error

Authors

Alexander Rakhlin, Xiyu Zhai

Topics

Machine Learning > Core Methods > Regression Machine Learning > Optimization & Theory > Statistical Learning Machine Learning > Optimization & Theory > Theory Machine Learning > Core Methods > Kernel Methods Machine Learning > Optimization & Theory > Generalization

Keywords

reproducing kernel hilbert space generalization error minimum norm interpolation kernel hilbert space laplace kernel kernel bandwidth high-dimensional phenomenon

More from COLT 2019

All COLT 2019 papers →

Affine Invariant Covariance Estimation for Heavy-Tailed Distributions

Stochastic Gradient Descent Learns State Equations with Nonlinear Activations

A Theory of Selective Prediction

Classification with unknown class-conditional label noise on non-compact feature spaces

The All-or-Nothing Phenomenon in Sparse Linear Regression

Depth Separations in Neural Networks: What is Actually Being Separated?