The Polynomial Approximation Barrier in High-Dimensional Kernels

This direction is split into other directions: polynomial approximation barrier. Its last version stays readable and citable here.

Version 1 of 19 papers33 conceptsfrozen 2026-10-04

In machine learning, kernel methods are often celebrated for their ability to map data into infinite-dimensional spaces, allowing linear algorithms to learn non-linear patterns. However, as the dimensionality of our data ($d$) grows, this "infinite" flexibility collapses into a surprisingly rigid structure. Recent research reveals that in high-dimensional regimes, standard kernels—like the Radial Basis Function (RBF) or the Neural Tangent Kernel (NTK)—behave less like universal approximators and more like simple polynomial regressions.

The Convergence to Polynomials

The intuition begins with the realization that kernels and polynomials are two sides of the same coin. Ross A. Lippert and Ryan M. Rifkin demonstrated in Asymptotics of Gaussian Regularized Least Squares that a Gaussian kernel isn't just a smoother; in the limit where the kernel bandwidth becomes very large and regularization vanishes, the kernel method mathematically converges to standard polynomial regression.

This happens because the Taylor expansion of the kernel function starts to dominate the learning process. If you discard the higher-order terms of this expansion—as many approximation techniques do—you lose the ability to represent anything beyond low-degree structures.

The Rotational Invariance Trap

Why do kernels struggle so much in high dimensions? The culprit is often rotational invariance. Most common kernels treat all directions in the input space as equally important. While this sounds fair, Konstantin Donhauser, Fanny Yang, and Mingqi Wu show in How rotational invariance of common kernels prevents generalization in high dimensions that this symmetry creates a "polynomial approximation barrier."

In high dimensions, a rotationally invariant kernel is biased toward low-degree polynomials. Unless the ground truth you are trying to learn is itself a simple polynomial, the kernel will fail to generalize. Because the kernel doesn't know which directions are relevant, it tries to approximate the function globally. In a space with hundreds of dimensions, the number of samples required to move beyond a low-degree approximation becomes astronomical.

The Staircase of Complexity

This limitation manifests as a "saturation effect." Work by Weihao Lu, Qian Lin, and colleagues in On the Saturation Effects of Spectral Algorithms in Large Dimensions describes a performance ceiling. Instead of a smooth learning curve, high-dimensional kernel methods often exhibit a "staircase" error curve.

The model's performance plateaus at a certain error level until the sample size hits a massive threshold, at which point it "unlocks" the ability to represent the next degree of polynomial complexity. If your target function is high-frequency or non-polynomial, you may never reach the next step of the staircase in practice.

Why Simple Projections Fail

One might hope to bypass this by projecting high-dimensional data onto lower-dimensional subspaces. While this works for linear classifiers, it fails for higher-degree models like Polynomial Threshold Functions (PTFs).

Lucas Slot, Stefan Tiegel, and Manuel Wiedmer point out in Testably Learning Polynomial Threshold Functions that high-degree functions create heavy-tailed distributions when projected. These heavy tails make it impossible for standard low-degree polynomials to accurately "fool" or approximate the function. To learn these complex boundaries, we need more than just one-dimensional views; we need techniques that account for the multidimensional interaction of features.

Breaking the Barrier

The consensus across these papers is that to move beyond simple polynomial approximations in high dimensions, we must break the symmetry. As Donhauser et al. suggest, incorporating structural priors—like translation invariance or specific covariance structures—allows the kernel to focus on relevant subspaces.

Without these priors, kernel methods in high dimensions remain "trapped" in a low-degree world, regardless of how much data we throw at them. Understanding this barrier is the first step toward designing kernels that can truly capture the complexity of high-dimensional reality.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_the_polynomial_approximation_barrier_in__b5f5573d,
  title = {The Polynomial Approximation Barrier in High-Dimensional Kernels},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-polynomial-approximation-barrier-in-high-dimensional-kernels/rdr_b5f5573d81934ab58d0370b0e58bdc44},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_the_polynomial_approximation_barrier_in__b5f5573d_v1,
  title = {The Polynomial Approximation Barrier in High-Dimensional Kernels},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-polynomial-approximation-barrier-in-high-dimensional-kernels/rdr_b5f5573d81934ab58d0370b0e58bdc44/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}