Harmless interpolation in regression and classification with structured features

Andrew D. McRae, Santhosh Karnik, Mark A. Davenport, Vidya K. Muthukumar

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:

  1. Consistent Everything: High noise-absorbing capacity allows both regression and classification to succeed.
  2. 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.
  3. Total Failure: Insufficient overparametrization fails to "hide" the noise, leading both tasks to fail.
Comparison of interpolation regimes for regression and classification.

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

Abstract

Overparametrized neural networks tend to perfectly fit noisy training data yet generalize well on test data. Inspired by this empirical observation, recent work has sought to understand this phenomenon of benign overfitting or harmless interpolation in the much simpler linear model. Previous theoretical work critically assumes that either the data features are statistically independent or the input data is high-dimensional; this precludes general nonparametric settings with structured feature maps. In this paper, we present a general and flexible framework for upper bounding regression and classification risk in a reproducing kernel Hilbert space. A key contribution is that our framework describes precise sufficient conditions on the data Gram matrix under which harmless interpolation occurs. Our results recover prior independent-features results (with a much simpler analysis), but they furthermore show that harmless interpolation can occur in more general settings such as features that are a bounded orthonormal system. Furthermore, our results show an asymptotic separation between classification and regression performance in a manner that was previously only shown for Gaussian features.
BibTeX
@inproceedings{mcrae2022harmless,
  author = {Andrew D. McRae and Santhosh Karnik and Mark A. Davenport and Vidya K. Muthukumar},
  title = {{Harmless interpolation in regression and classification with structured features}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=GoMfjVA4Ou9},
}
Figure