Abstract
Kernel ridge regression (KRR) is a cornerstone of machine learning, achieving minimax optimal rates in low-dimensional settings. However, its performance in high-dimensional regimes—where the number of features $d$ is comparable to or exceeds the number of samples $n$—is less understood. This paper demonstrates that the rotational invariance inherent in common kernels (e.g., RBF, Laplace, NTK) induces a mathematical bias towards low-degree polynomials in high dimensions. We establish lower bounds on the generalization error across various distributions and kernel scalings, suggesting that consistency in high dimensions requires structural priors beyond simple eigenvalue decay.
Introduction: The High-Dimensional Wall
In modern machine learning, we frequently encounter datasets where the dimensionality $d$ is significantly larger than the sample size $n$. While KRR excels in low dimensions, it often hits a "polynomial barrier" in high-dimensional spaces, failing to learn functions more complex than simple polynomials. This research investigates whether this failure is a universal property of rotationally invariant kernels or a consequence of specific data distributions.
Theoretical Framework and Methods
The authors analyze the bias component of generalization error for a broad class of rotationally invariant kernels. These kernels depend only on the relative geometry (distance or angle) of points, not their absolute orientation. The study covers:
- Broad Kernel Classes: Including Gaussian (RBF), Laplace, Inner Product, and Neural Tangent Kernels (NTK) of any depth.
- General Distributions: Extending beyond spherical data to anisotropic Gaussians and other covariance models.
- Concentration of Measure: Utilizing high-dimensional probability tools to show that kernel matrices "collapse" as $d$ grows, losing the ability to resolve complex signals.
- The Flat Limit: Proving that the polynomial barrier persists even when kernels are scaled to be extremely smooth.
Key Insights: The Curse of Symmetry
Rotational invariance is a common default because it treats all feature directions equally. However, in high dimensions, this lack of prior knowledge becomes a liability. It creates an inductive bias so strong that the model cannot "see" complex interactions between features. This "polynomial approximation barrier" is shown to be a fundamental limitation whenever the effective dimension of the data is high.
Furthermore, the research identifies a U-shaped risk curve in sparse settings. While adding relevant features initially improves performance, the introduction of too many irrelevant features triggers the high-dimensional bias, causing performance to degrade. This suggests that feature selection or structural priors are essential for success in high dimensions.
Results and Empirical Validation
The core theoretical result (Theorem 3.1) provides a lower bound on the bias of KRR. If the relationship between dimensions and samples is $d \approx n^\beta$, the model is restricted to learning polynomials of degree approximately $2/\beta$.
Empirical tests on the Residential Building dataset (UCI) confirmed these findings. The prediction error reached a minimum at 25 features but increased significantly as the full set of 107 features was used, demonstrating that high dimensionality actively hindered generalization. Similar results were observed in high-dimensional leukemia classification datasets (ALLAML, CLL_SUB_111), where $d \gg n$.
Conclusion
The results imply that achieving consistency in high-dimensional learning requires "breaking" rotational symmetry. This explains the superior performance of architectures like Convolutional Neural Networks (CNNs), which incorporate spatial structure as an inductive prior rather than treating all feature permutations as equal. Future work will focus on tightening these lower bounds and quantifying the exact amount of structural information needed to overcome the high-dimensional wall.
Summary updated