Kernel Ridgeless Regression is Inconsistent for Low Dimensions

Daniel Beaglehole, Mikhail Belkin, Parthe PanditarXiv 2022 · OpenReview

Introduction

In the era of deep learning, the phenomenon of "benign overfitting" has challenged classical statistical intuition. Traditional learning theory suggests a strict bias-variance tradeoff: models that perfectly interpolate noisy training data should suffer from high variance and poor generalization. However, modern high-dimensional models—ranging from deep neural networks to overparameterized linear regressions—often achieve zero training error while maintaining excellent test performance.

This "interpolation magic" has largely been studied in high-dimensional regimes where the number of features grows alongside the sample size. This paper investigates whether this property holds for kernel machines in fixed, low-dimensional spaces. Specifically, it examines Kernel Ridgeless Regression (KRR) and proves that for common kernels like Gaussian, Laplace, and Cauchy, forcing the model to interpolate noisy data ensures it will never converge to the true underlying function, regardless of the sample size.

The Problem: Interpolation in Low Dimensions

The central question is whether benign overfitting is a universal property or a consequence of high dimensionality. In low dimensions (e.g., 1D or 2D), does a kernel interpolator eventually "learn" the truth as more data is collected?

Kernel Ridgeless Regression seeks a function $f$ in a Reproducing Kernel Hilbert Space (RKHS) that minimizes the norm $\|f\|_{\mathcal{H}}$ subject to the constraint $f(x_i) = y_i$ for all training points. When the labels $y_i$ contain noise, the model is forced to pass through every noisy point. The authors demonstrate that in fixed dimensions, this requirement is catastrophic for generalization.

Methodology: Fourier Analysis and MSE Decomposition

The authors employ a rigorous mathematical framework using Fourier analysis to study translation-invariant kernels—those where $K(x, y) = \phi(x - y)$. By analyzing the "spectrum" or Fourier coefficients of these kernels, they decompose the Mean Squared Error (MSE) of the kernel interpolator into three components:

  1. Approximation Error: The inherent limitation of the kernel's span in representing the target function $f^*$.
  2. Noise-free Estimation Error: The error arising from sampling a finite number of points, even in the absence of noise.
  3. Noisy Estimation Error: The error specifically induced by the model's attempt to interpolate the random noise in the labels.

This decomposition allows the authors to track how each error component behaves as the number of samples $n$ increases. They specifically study data arranged on a unit circle ($d=1$) and a multidimensional torus ($d > 1$) to prove their theorems.

The Bandwidth Trap

A critical factor in kernel methods is the "bandwidth" parameter ($M$), which dictates the smoothness of the resulting function. The research reveals a fatal trade-off in low dimensions:

  • High Bandwidth: To suppress the "Noisy Estimation Error," one might increase the bandwidth to smooth out the noise. However, this causes the "Approximation Error" to explode, as the model becomes too rigid to capture the underlying signal.
  • Low Bandwidth: Conversely, a small bandwidth allows the model to approximate the target function well but makes it hyper-sensitive to noise, leading to "jagged" interpolants that fail to generalize.

In high dimensions, noise is "diluted" across many orthogonal directions, allowing the model to interpolate without significantly distorting the global structure. In low dimensions, there is "nowhere for the noise to hide." The model must create sharp, local spikes to meet the interpolation constraints, which fundamentally ruins the estimation.

Theoretical and Empirical Results

The paper provides formal proofs (Theorems 4.3, 4.4, and 4.5) demonstrating that for Gaussian, Laplace, and Cauchy kernels, the MSE remains bounded away from zero as $n \to \infty$. This implies that these estimators are "inconsistent"—they never converge to the true function.

Numerical simulations support these findings. When attempting to recover a simple cosine wave $f^*(x) = \cos(x)$ from noisy samples, the authors observed that:

  • With small bandwidth, the interpolator appears as a piecewise linear, jagged mess.
  • With large bandwidth, the model simply collapses toward zero, failing to capture the oscillation of the cosine wave.

In no scenario does the ridgeless interpolator recover the true signal effectively, regardless of how the bandwidth is tuned.

Conclusion and Implications

The findings suggest that the "blessing of dimensionality" is a prerequisite for benign overfitting in kernel methods. In low-dimensional settings, the classical wisdom of the bias-variance tradeoff remains dominant.

For practitioners, the takeaway is clear: when working with low-dimensional data, regularization (Kernel Ridge Regression) is not optional. One cannot rely on the implicit regularization of the interpolation process to achieve consistency. Furthermore, this work has implications for deep learning. Since infinitely-wide neural networks can be characterized by the Neural Tangent Kernel (NTK), these results suggest that such networks might also be inconsistent in low dimensions if forced to interpolate. Future research is needed to determine if the "feature learning" capabilities of finite-width networks allow them to bypass these limitations.

Summary updated

BibTeX
@misc{beaglehole2022kernel,
  author = {Daniel Beaglehole and Mikhail Belkin and Parthe Pandit},
  title = {{Kernel Ridgeless Regression is Inconsistent for Low Dimensions}},
  year = {2022},
  url = {https://openreview.net/forum?id=sWpi58N5m4T},
}
Figure