The Polynomial Approximation Barrier in High Dimensions

17 concepts3 papers1 proposal

Kernel methods are a cornerstone of non-linear machine learning, yet they face a dual crisis when applied to high-dimensional data. This crisis is both computational—where the cost of approximating complex kernels scales exponentially with dimensionality—and statistical—where the inherent symmetry of common kernels prevents them from learning complex functions. Together, these limitations form what is known as the polynomial approximation barrier.

The Computational Cost of Complexity

To make kernel methods scalable, researchers often use "sketches" or explicit feature maps to approximate the kernel function. However, as Ha Quang et al. observe in Kernel Methods on Approximate Infinite-Dimensional Covariance Operators for Image Classification, while shift-invariant kernels can be approximated for distance calculations, inner products in high-dimensional spaces are notoriously difficult to estimate. This is particularly problematic for polynomial kernels, which rely on these inner products to capture non-linear feature correlations.

The difficulty intensifies as the degree of the polynomial increases. Traditionally, sketching a polynomial kernel of degree $p$ required resources that grew exponentially with $p$, a phenomenon often called the "curse of dimensionality." In Oblivious Sketching of High-Degree Polynomial Kernels, Kapralov et al. address this by introducing a "recursive tensoring" technique. Their approach breaks the exponential dependence on the degree, providing a path to approximate high-dimensional Gaussian and radial basis function (RBF) kernels without the typical dimension-dependent overhead.

The Statistical Blind Spot of Rotational Invariance

Even if we can compute these kernels efficiently, a deeper statistical problem remains. Most popular kernels, including the RBF and the Neural Tangent Kernel (NTK), are rotationally invariant. This means they treat all directions in the input space as equally important.

In high-dimensional settings where the number of features $d$ is comparable to the number of samples $n$, this symmetry becomes a liability. As Donhauser et al. demonstrate in How rotational invariance of common kernels prevents generalization in high dimensions, rotationally invariant kernels are subject to a strict polynomial approximation barrier. The authors prove that these models are biased toward low-degree polynomials; they can only consistently learn the simple, global components of a target function and fail to capture complex, non-polynomial relationships.

The intuition is that in high dimensions, a rotationally invariant kernel cannot "pick out" the specific, informative directions amidst the noise. Because it assigns equal weight to every direction, the estimator defaults to a simple global average—a low-degree polynomial approximation—rather than identifying the specific features necessary for high-quality generalization.

Overcoming the Barrier

The research suggests that the path forward requires breaking the very symmetries that make these kernels "general purpose." Donhauser et al. argue that to move beyond the polynomial approximation barrier, models must incorporate architectural inductive biases or manual feature selection that prioritize specific data structures, such as spatial locality.

By moving away from generic rotational invariance and toward models that can isolate informative directions, practitioners can overcome the "blind spot" that limits kernel methods in high-dimensional spaces. This shift explains why specialized architectures, which break rotational symmetry by design, consistently outperform generic kernel methods on complex, high-dimensional tasks.

Key Foundational Work

Oblivious Sketching of High-Degree Polynomial Kernels (2019) — contributed 1 concept elements to this direction.
Kernel Methods on Approximate Infinite-Dimensional Covariance Operators for Image Classification (2016) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_polynomial_approximation_barrier_4e0abb47,
  title = {polynomial approximation barrier},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/polynomial-approximation-barrier/rdr_4e0abb47c2674e158c2a3c093831f1a5},
  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_polynomial_approximation_barrier_4e0abb47_v1,
  title = {polynomial approximation barrier},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/polynomial-approximation-barrier/rdr_4e0abb47c2674e158c2a3c093831f1a5/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake