Abstract
Modern deep learning models often interpolate noisy training data perfectly while maintaining high generalization performance, a phenomenon known as benign overfitting. This paper provides a theoretical framework for harmless interpolation that moves beyond restrictive assumptions of high-dimensionality or feature independence. By analyzing Kernel Ridge Regression with structured features like Fourier series, the authors demonstrate that classification is significantly more robust than regression in the interpolating regime, where a model can be a poor regressor but a highly accurate classifier.
Introduction
In classical statistics, overfitting is typically viewed as a failure of generalization. However, the success of overparametrized neural networks has challenged this view. Most existing mathematical explanations for this "harmless interpolation" require either extremely high-dimensional inputs or statistically independent features. This paper bridges the gap by providing a theory applicable to structured features and low-dimensional data, such as 1D signals represented by Fourier series.
Methodology
The authors analyze Kernel Ridge Regression and the minimum-norm interpolator within a Reproducing Kernel Hilbert Space (RKHS). Their approach focuses on the properties of the Gram matrix rather than raw features. Key technical components include:
- Bi-level Ensemble Analysis: Modeling the data spectrum with "large" eigenvalues for signal and "small" eigenvalues for noise absorption.
- Bounded Orthonormal Systems (BOS): Extending theory to common bases like sinusoids and Chebyshev polynomials.
- Bias-Variance Decomposition: Providing non-asymptotic risk bounds to separate signal preservation from noise reaction.
Key Results and Insights
The study identifies three distinct regimes as the number of samples $n$ increases:
- Consistent Everything: High noise-absorbing capacity allows both regression and classification to succeed.
- Regression Failure: The model fits noise in a way that ruins numerical predictions (inconsistent regression), yet the sign of the prediction remains correct, preserving classification accuracy.
- Total Failure: Insufficient overparametrization fails to "hide" the noise, leading both tasks to fail.
The "aha moment" of this research is that classification is more forgiving than regression. While regression error explodes when predictions are slightly off, classification error remains zero as long as the prediction maintains the correct sign. This separation allows for successful classification even when regression performance is poor, as shown in the transition between panels (b) and (c) in the figure above.
Limitations and Future Work
Current proofs assume the target function $f^*$ lies within the span of the kernel's top eigenfunctions. Future work should extend this to more general functions in the RKHS. Additionally, establishing lower bounds would determine the tightness of the current theory. Finally, exploring the formal equivalence to max-margin Support Vector Machines (SVMs) in structured settings remains an open area for investigation.
Summary updated