Abstract
The generalization ability of kernel interpolation in large dimensions (where the number of samples $n$ scales with the dimension $d$ as $n \asymp d^{\gamma}$) is a central question in understanding the "benign overfitting" phenomenon observed in deep learning. By focusing on inner product kernels on the sphere, this research fully characterizes the exact order of variance and bias under various source conditions $s \geq 0$. The resulting $(s, \gamma)$-phase diagram identifies the specific regions where kernel interpolation is minimax optimal, sub-optimal, or inconsistent.
Introduction
In classical statistical theory, the "bias-variance tradeoff" suggests that a model that fits training data perfectly—interpolating the noise—will generalize poorly. However, modern neural networks often operate in an overparameterized regime where they interpolate noisy data yet achieve excellent test performance. This phenomenon, known as "benign overfitting," has prompted a re-evaluation of interpolation.
To provide a theoretical foundation for this behavior, researchers often study kernel interpolation, which serves as a tractable proxy for infinite-width neural networks. This paper investigates the "large-dimensional" regime, where the number of samples $n$ and the dimension $d$ both grow to infinity such that $n \asymp d^\gamma$ for some $\gamma > 0$. The goal is to determine the precise conditions under which kernel interpolation achieves minimax optimal generalization.
Mathematical Framework
The study focuses on inner product kernels defined on the unit sphere $S^d$ in $\mathbb{R}^{d+1}$, with data points sampled from a uniform distribution. The target function $f^*$ is assumed to satisfy a source condition $s$, a parameter that quantifies the smoothness of the function (higher $s$ indicates a smoother function).
The researchers utilized several key analytical tools:
- Spectral Analysis: Decomposing the kernel into eigenvalues and eigenfunctions (spherical harmonics).
- Bias-Variance Decomposition: Separating the generalization error into a variance term (error stemming from noise) and a bias term (error from the model's structural limitations).
- Asymptotic Analysis: Deriving matching upper and lower bounds to establish the exact convergence rates as $d \to \infty$.
The $(s, \gamma)$-Phase Diagram
The core contribution of this work is the characterization of the $(s, \gamma)$-phase diagram, which maps the relationship between function smoothness ($s$) and the data scaling exponent ($\gamma$). The diagram reveals three distinct performance regimes:
- Minimax Optimal: In this region, kernel interpolation achieves the best possible theoretical error rate for the given class of functions.
- Sub-optimal: The model remains consistent (error vanishes as $n \to \infty$), but its convergence rate is slower than the theoretical optimum.
- Inconsistent: The generalization error fails to vanish, even in the limit of infinite data.
The Smoothness Paradox
A surprising finding is the existence of an optimality threshold $\Gamma(\gamma)$. While one might expect smoother functions to be easier to learn, the authors discovered that if a function is too smooth ($s > \Gamma(\gamma)$), kernel interpolation becomes sub-optimal. This occurs because the minimum-norm requirement of interpolation forces the model to introduce high-frequency components to fit the noise, which disproportionately degrades the fit for very smooth underlying functions.
Integer Instability
The analysis shows that kernel interpolation becomes inconsistent whenever $\gamma$ is an integer. This phenomenon is linked to the "polynomial approximation barrier." When the number of samples is just sufficient to transition between learning different degrees of spherical harmonics, the model's variance spikes, preventing consistency.
Key Results and Convergence Rates
The authors established the exact order of variance as: $$\text{var} \asymp d^{l-\gamma} + d^{\gamma-l-1}$$ where $l = \lfloor \gamma \rfloor$. This formula highlights the sensitivity of the model to the relationship between sample size and dimensionality.
Furthermore, the research proves that kernel interpolation is consistent if and only if $s > 0$ and $\gamma$ is not an integer. When $0 < s \leq \Gamma(\gamma)$, the method is confirmed to be minimax optimal, providing a rigorous theoretical justification for interpolation in high-dimensional settings.
Discussion and Limitations
While this work provides a comprehensive map of kernel interpolation behavior, it is bounded by certain geometric and model constraints. The results are derived for data distributed uniformly on a sphere and for inner product kernels. While these are standard theoretical benchmarks, real-world data often resides on more complex, low-dimensional manifolds, and different kernel architectures (beyond the Neural Tangent Kernel) may exhibit different phase transitions.
Future research may extend these findings by exploring more general hypercontractivity conditions, potentially broadening the applicability of the $(s, \gamma)$-phase diagram to a wider range of data distributions and kernel types.
Summary updated