Just Interpolate: Kernel "Ridgeless" Regression Can Generalize

Abstract

In the absence of explicit regularization, Kernel "Ridgeless" Regression with nonlinear kernels has the potential to fit the training data perfectly. It has been observed empirically, however, that such interpolated solutions can still generalize well on test data. We isolate a phenomenon of implicit regularization for minimum-norm interpolated solutions which is due to a combination of high dimensionality of the input data, curvature of the kernel function, and favorable geometric properties of the data such as an eigenvalue decay of the empirical covariance and kernel matrices. In addition to deriving a data-dependent upper bound on the out-of-sample error, we present experimental evidence suggesting that the phenomenon occurs in the MNIST dataset.

arXiv comment28 pages, 8 figures

References in corpus (8)

• Scikit-learn: Machine Learning in Python
• Understanding deep learning requires rethinking generalization
• Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate
• In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning
• The spectrum of kernel random matrices
• To understand deep learning we need to understand kernel learning
• Training Neural Networks as Learning Data-adaptive Kernels: Provable Representation and Approximation Benefits
• Approximation beats concentration? An approximation view on inference with smooth radial kernels

Cited by in corpus (24)

• Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networks
• Exploring Deep Neural Networks via Layer-Peeled Model: Minority Collapse in Imbalanced Training
• Memorizing without overfitting: Bias, variance, and interpolation in over-parameterized models
• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-${\ell }_1$-Norm Interpolated Classifiers
• A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descent
• Kernel Two-Sample Tests in High Dimension: Interplay Between Moment Discrepancy and Dimension-and-Sample Orders
• HARFE: Hard-Ridge Random Feature Expansion
• Training Neural Networks as Learning Data-adaptive Kernels: Provable Representation and Approximation Benefits
• The Training Process of Many Deep Networks Explores the Same Low-Dimensional Manifold
• Tractability from overparametrization: The example of the negative perceptron
• Mehler's Formula, Branching Process, and Compositional Kernels of Deep Neural Networks
• On generalization bounds for deep networks based on loss surface implicit regularization
• Thermodynamic limit in learning period three
• New Equivalences Between Interpolation and SVMs: Kernels and Structured Features
• Which Minimizer Does My Neural Network Converge To?
• Kernel interpolation generalizes poorly
• Convergence Conditions for Stochastic Line Search Based Optimization of Over-parametrized Models
• The Directional Bias Helps Stochastic Gradient Descent to Generalize in Kernel Regression Models
• Universal Prediction Band via Semi-Definite Programming
• Generalization Error Curves for Analytic Spectral Algorithms under Power-law Decay
• The High-Dimensional Asymptotics of Principal Component Regression
• Using Neural Networks to Accelerate TALYS-2.0 Nuclear Reaction Simulations
• Effectively Leveraging Momentum Terms in Stochastic Line Search Frameworks for Fast Optimization of Finite-Sum Problems
• Bias-variance decomposition of overparameterized regression with random linear features