How rotational invariance of common kernels prevents generalization in high dimensions

2021/04/09 by Konstantin Donhauser, Donhauser, Konstantin, Mingqi Wu +3 · 10 citations
Computer Science · Engineering · Materials Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Gaussian Processes and Bayesian Inference #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and ELM #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST) #Stochastic Gradient Optimization Techniques #Thermal properties of materials #cs.LG #math.ST #stat.ML #stat.TH

paper · pdf · doi:10.48550/arxiv.2104.04244

arxiv created 2021/04/09 · openalex publication_date 2021/04/09 · arxiv updated 2021/04/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Kernel ridge regression is well-known to achieve minimax optimal rates in low-dimensional settings. However, its behavior in high dimensions is much less understood. Recent work establishes consistency for kernel regression under certain assumptions on the ground truth function and the distribution of the input data. In this paper, we show that the rotational invariance property of commonly studied kernels (such as RBF, inner product kernels and fully-connected NTK of any depth) induces a bias towards low-degree polynomials in high dimensions. Our result implies a lower bound on the generalization error for a wide range of distributions and various choices of the scaling for kernels with different eigenvalue decays. This lower bound suggests that general consistency results for kernel ridge regression in high dimensions require a more refined analysis that depends on the structure of the kernel beyond its eigenvalue decay.

Cited by

• Sharp convergence rates for Spectral methods via the feature space decomposition method
• A general technique for approximating high-dimensional empirical kernel matrices
• Transfer Learning for Benign Overfitting in High-Dimensional Linear Regression
• Mamba Can Learn Low-Dimensional Targets In-Context via Test-Time Feature Learning
• Kernel ridge regression under power-law data: spectrum and generalization
• Test time training enhances in-context learning of nonlinear functions
• Feature learning is decoupled from generalization in high capacity neural networks
• IIKL: Isometric Immersion Kernel Learning with Riemannian Manifold for Geometric Preservation
• Characterising the Inductive Biases of Neural Networks on Boolean Data
• Learning Curves of Stochastic Gradient Descent in Kernel Regression

Related

• A Geometrical Analysis of Kernel Ridge Regression and its Applications
• Optimal Rates of Kernel Ridge Regression under Source Condition in Large Dimensions
• Failure and success of the spectral bias prediction for Kernel Ridge Regression: the case of low-dimensional data
• Kernel ridge regression under power-law data: spectrum and generalization
• Kernel regression in high dimensions: Refined analysis beyond double descent