This paper provides a sobering look at why some of our most trusted tools in machine learning—rotationally invariant kernels—struggle when faced with high-dimensional data.
Commonly used kernels, such as Radial Basis Functions (RBF), Laplace, and Neural Tangent Kernels (NTK), suffer from a "polynomial approximation barrier" in high dimensions. This means they can only consistently learn functions that are low-degree polynomials. This failure is fundamentally tied to their rotational symmetry, suggesting that to succeed in high dimensions, we must use kernels that incorporate specific structural prior knowledge to break this symmetry.
The High-Dimensional Dilemma
Kernel Ridge Regression (KRR) is a cornerstone of non-parametric statistics, well-known for achieving optimal learning rates in low-dimensional settings. However, modern datasets often feature a dimensionality ($d$) that is nearly as large as the number of samples ($n$). In this high-dimensional regime, our understanding of KRR has historically been much murkier.
Previous research offered conflicting views. Some theoretical work suggested KRR could be consistent—learning the true function perfectly as $n \to \infty$—in high dimensions. Conversely, other "lower bound" results demonstrated a polynomial approximation barrier, suggesting these models essentially degenerate and can only represent simple polynomial versions of complex ground truths.
The authors of this paper resolve these contradictions. They demonstrate that many previous consistency results relied on an assumption (a bounded RKHS norm) that is almost always violated as dimensionality increases. They prove that the polynomial barrier is a general, unavoidable phenomenon for any rotationally invariant kernel in high dimensions.
Methodology
The authors analyze the high-dimensional asymptotic regime where both $n$ and $d$ go to infinity, specifically looking at the scaling $d/n^\beta \to c$ (where $\beta$ controls how fast the dimension grows relative to the sample size).
Their primary contribution is a unified theoretical framework that proves lower bounds on the generalization error (bias) for a broad class of kernels and data distributions:
- Kernels: The analysis covers rotationally invariant kernels, including RBF, inner product kernels, and fully-connected NTKs of any depth.
- Distributions: Unlike previous work limited to data on a sphere, this framework covers general covariance models, including anisotropic Gaussians.
- The "Flat Limit": The authors extend their analysis to show that the barrier persists even when the kernel is scaled to be extremely "flat."
The paper validates these theoretical findings using a mix of synthetic data (random vectors generated from various covariance models) and real-world data (the Residential Housing dataset from the UCI repository).
Key Insights
The Symmetry Trap
Rotational invariance means the kernel treats all directions in the input space equally. While this seems like a safe, "neutral" choice, it becomes a massive liability in high dimensions. It forces the estimator to behave like a low-degree polynomial because it cannot "focus" on the specific directions that actually matter for the task.
RKHS Norm Explosion
A crucial breakthrough in the paper is the demonstration that even for a simple linear function like $f(x) = x_1$, the norm in the Reproducing Kernel Hilbert Space (RKHS) diverges to infinity as $d$ grows. This explains why previous "upper bound" proofs—which assumed bounded norms—failed to predict the barrier.
Stepwise Learning
As the ratio of $d$ to $n$ changes (parameterized by $\beta$), the kernel "unlocks" the ability to learn higher-degree polynomials. However, it is always lagging behind the true complexity of a non-polynomial function.
Key Results
- The Polynomial Barrier: The authors mathematically prove that the bias of the kernel estimator is lower-bounded by the error of approximating the ground truth with a polynomial of degree $m$ (where $m$ depends on the scaling factor $\beta$).
- Visualizing Degeneration: When trying to fit a complex function like a sine wave, the kernel estimator works perfectly at $d=1$. However, as the dimension $d$ increases, the estimator flattens out, eventually degenerating into a simple linear approximation.
- The U-Shaped Risk Curve: In experiments with sparse ground truths (functions depending only on a few features), the authors found a U-shaped risk curve. Adding relevant features initially reduces bias. But as more features are added—even irrelevant ones—the high-dimensional nature of the problem kicks in, the polynomial barrier takes over, and the bias starts increasing again.
Limitations and Future Work
While the results are asymptotic ($n, d \to \infty$), they closely match empirical observations for relatively small sample sizes and dimensions (e.g., $n=2000, d=50$). Providing explicit non-asymptotic bounds remains an open challenge. Additionally, the authors acknowledge that their bound might not be perfectly tight compared to some highly specific settings studied in other papers, as they prioritized a more general proof framework.
The most important takeaway is the critical need for kernels that break rotational symmetry. The authors point to convolutional neural tangent kernels (CNTKs) as a successful example in computer vision, where the kernel's structure reflects the spatial translation invariance of images rather than general rotational invariance. Future work must focus on how to systematically design such "asymmetric" kernels for other types of high-dimensional data.
Summary updated