Generalization error of minimum weighted norm and kernel interpolation

Abstract

We study the generalization error of functions that interpolate prescribed data points and are selected by minimizing a weighted norm. Under natural and general conditions, we prove that both the interpolants and their generalization errors converge as the number of parameters grow, and the limiting interpolant belongs to a reproducing kernel Hilbert space. This rigorously establishes an implicit bias of minimum weighted norm interpolation and explains why norm minimization may either benefit or suffer from over-parameterization. As special cases of this theory, we study interpolation by trigonometric polynomials and spherical harmonics. Our approach is from a deterministic and approximation theory viewpoint, as opposed to a statistical or random matrix one.

arXiv comment31 pages, 2 figures. To appear in SIAM Journal on Mathematics of Data Science

References in corpus (12)

• Reconciling modern machine learning practice and the bias-variance trade-off
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Benign Overfitting in Linear Regression
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• On Lazy Training in Differentiable Programming
• 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
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Multiple Descent: Design Your Own Generalization Curve
• Failures of model-dependent generalization bounds for least-norm interpolation
• Kernel regression in high dimensions: Refined analysis beyond double descent
• Interpolation and Learning with Scale Dependent Kernels