Kernel regression in high dimensions: Refined analysis beyond double descent

Abstract

In this paper, we provide a precise characterization of generalization properties of high dimensional kernel ridge regression across the under- and over-parameterized regimes, depending on whether the number of training data n exceeds the feature dimension d. By establishing a bias-variance decomposition of the expected excess risk, we show that, while the bias is (almost) independent of d and monotonically decreases with n, the variance depends on n, d and can be unimodal or monotonically decreasing under different regularization schemes. Our refined analysis goes beyond the double descent theory by showing that, depending on the data eigen-profile and the level of regularization, the kernel regression risk curve can be a double-descent-like, bell-shaped, or monotonic function of n. Experiments on synthetic and real data are conducted to support our theoretical findings.

arXiv commentThis paper was accepted by AISTATS-2021

References in corpus (16)

• Reconciling modern machine learning practice and the bias-variance trade-off
• Understanding deep learning requires rethinking generalization
• Fast rates for support vector machines using Gaussian kernels
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Generalization Properties of Learning with Random Features
• Orthogonal Random Features
• Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
• Optimal Regularization Can Mitigate Double Descent
• The Neural Tangent Kernel in High Dimensions: Triple Descent and a Multi-Scale Theory of Generalization
• Exact expressions for double descent and implicit regularization via surrogate random design
• Optimal learning rates for Kernel Conjugate Gradient regression
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• Asymptotics of Ridge (less) Regression under General Source Condition
• Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm
• On the Sample Complexity of Subspace Learning
• Interpolation and Learning with Scale Dependent Kernels

Cited by in corpus (7)

• Learning curves of generic features maps for realistic datasets with a teacher-student model
• Understanding Generalization in Adversarial Training via the Bias-Variance Decomposition
• Dimensionality reduction, regularization, and generalization in overparameterized regressions
• Generalization Error Curves for Analytic Spectral Algorithms under Power-law Decay
• Adversarially Robust Kernel Smoothing
• Generalization error of minimum weighted norm and kernel interpolation
• How rotational invariance of common kernels prevents generalization in high dimensions