Characterizing Overfitting in Kernel Ridgeless Regression Through the Eigenspectrum

2024/02/02 by Tin Sum Cheng, Cheng, Tin Sum, Aurélien Lucchi +5 · 3 citations
Computer Science · Decision Sciences · Engineering · #FOS: Computer and information sciences #Face and Expression Recognition #Grey System Theory Applications #Infrared Target Detection Methodologies #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · pdf · doi:10.48550/arxiv.2402.01297

openalex publication_date 2024/02/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We derive new bounds for the condition number of kernel matrices, which we then use to enhance existing non-asymptotic test error bounds for kernel ridgeless regression (KRR) in the over-parameterized regime for a fixed input dimension. For kernels with polynomial spectral decay, we recover the bound from previous work; for exponential decay, our bound is non-trivial and novel. Our contribution is two-fold: (i) we rigorously prove the phenomena of tempered overfitting and catastrophic overfitting under the sub-Gaussian design assumption, closing an existing gap in the literature; (ii) we identify that the independence of the features plays an important role in guaranteeing tempered overfitting, raising concerns about approximating KRR generalization using the Gaussian design assumption in previous literature.

Cited by

• When Bias Pretends to Be Truth: How Spurious Correlations Undermine Hallucination Detection in LLMs
• Spectral Analysis of Molecular Kernels: When Richer Features Do Not Guarantee Better Generalization
• Beyond Universal Approximation Theorems: Algorithmic Uniform Approximation by Neural Networks Trained with Noisy Data

Related

• Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality
• An Agnostic View on the Cost of Overfitting in (Kernel) Ridge Regression
• On the Inconsistency of Kernel Ridgeless Regression in Fixed Dimensions
• Generalization in Kernel Regression Under Realistic Assumptions
• A Geometrical Analysis of Kernel Ridge Regression and its Applications