How rotational invariance of common kernels prevents generalization in high dimensions

Konstantin Donhauser, Mingqi Wu, Fanny Yang

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.

As dimensionality $d$ increases, the kernel estimator fails to capture high-frequency components of the ground truth, effectively degenerating into a low-degree polynomial approximation.

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:

  1. Broad Kernel Classes: Including Gaussian (RBF), Laplace, Inner Product, and Neural Tangent Kernels (NTK) of any depth.
  2. General Distributions: Extending beyond spherical data to anisotropic Gaussians and other covariance models.
  3. Concentration of Measure: Utilizing high-dimensional probability tools to show that kernel matrices "collapse" as $d$ grows, losing the ability to resolve complex signals.
  4. 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$.

The normalized bias exhibits a step-wise increase as the scaling parameter $\beta$ changes, confirming the theoretical prediction that higher dimensions restrict the model to lower-degree polynomial approximations.

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

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.
BibTeX
@inproceedings{donhauser2021how,
  author = {Konstantin Donhauser and Mingqi Wu and Fanny Yang},
  title = {{How rotational invariance of common kernels prevents generalization in high dimensions}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=qMMj42T-_hY},
}

Loading related content...

Figure