Near-Interpolators: Rapid Norm Growth and the Trade-Off between Interpolation and Generalization

Yutong Wang, Rishi Sonthalia, Wei Hu

TL;DR

This paper reveals that "near-interpolating" models, which achieve very low but not zero training error, exhibit surprisingly rapid norm growth. This finding suggests that existing generalization bounds, which rely on model norms, are too loose for these practical scenarios. The authors also provide a precise characterization of the trade-off between how well a model interpolates the data and its ability to generalize to unseen data, showing that certain data properties (specifically, eigenvalue decay) worsen this trade-off.

What Problem Does This Paper Address?

In machine learning, particularly with overparameterized models (where the number of parameters exceeds the number of data points), achieving zero training error (perfect interpolation) is often possible. However, it's widely believed that this can lead to overfitting and poor generalization. Techniques like regularization and early stopping are used to prevent perfect interpolation, aiming for "near-interpolation" – very low training error, but not zero. A key question has been: how do these near-interpolators generalize? While the phenomenon of "benign overfitting" has been studied for perfect interpolators (where they generalize surprisingly well), the behavior of near-interpolators, which are more practically relevant, remained less understood. Specifically, the paper addresses:

  1. The norm growth of near-interpolators: Do their parameters (norms) grow unboundedly, and if so, how fast?
  2. The interpolation-generalization trade-off: How does the ability to get closer to zero training error affect test error, and what data characteristics influence this relationship?

Methods

The authors employ a combination of random matrix theory (RMT) and theoretical analysis to study linear regression models.

  • Random Matrix Theory: They make assumptions about the data distribution and the covariance matrix of the features. Specifically, they assume a power-law spectrum for the covariance matrix ($\lambda_i(\boldsymbol{\Sigma}) \sim i^{-\alpha}$), which is a common characteristic observed in real-world data and neural network kernels. This allows them to analyze the behavior of models in the high-dimensional limit (where the number of samples and features grow large together).
  • Theoretical Analysis:
    • They derive norm growth bounds for near-interpolating ridge regressors, showing that their norms grow polynomially with the number of samples ($ \mathbb{E}[\|{\boldsymbol{\beta}}\|_{2}^{2}] = \Omega(n^{\alpha})$).
  • They develop an "eigenlearning framework" (building on prior work) to precisely characterize the asymptotic trade-off between training and testing error. This framework allows them to derive an exact formula relating these two quantities, parameterized by the data's eigenvalue decay exponent ($\alpha$) and the desired level of interpolation.
  • They connect their theoretical findings to early-stopped shallow neural networks, suggesting that similar phenomena might occur.

Datasets

The paper uses synthetic data generated according to the High-Dimensional Asymptotic (HDA) model with power-law spectra. They also conduct experiments on real-world datasets from the UCI regression collection, specifically the forest and stock datasets. For these real-world datasets, they use neural tangent kernels (NTKs) to analyze their spectral properties.

Key Insights and Ideas

  • Near-interpolation isn't necessarily "safe": While perfect interpolators can sometimes generalize well (benign overfitting), near-interpolators, especially those with data exhibiting strong eigenvalue decay (large $\alpha$), can have rapidly growing norms. This growth is so significant that it renders standard, data-independent norm-based generalization bounds ineffective (too loose).
  • Data structure matters critically: The rate at which the eigenvalues of the data covariance matrix decay (captured by the exponent $\alpha$) directly impacts the interpolation-generalization trade-off. A faster decay (larger $\alpha$) leads to a worse trade-off, meaning you get less generalization benefit for getting closer to zero training error.
  • A precise trade-off curve: The authors provide an explicit formula that maps the training error to the testing error, modulated by the data's spectral properties. This offers a quantitative understanding of how much generalization you sacrifice for a given level of interpolation.
  • Empirical validation: The theoretical findings about norm growth and the trade-off are empirically validated on both synthetic linear models and, importantly, on neural networks trained on real-world datasets. This suggests the theoretical insights have practical relevance beyond simple linear models.

Key Results

  • Rapid Norm Growth: For near-interpolating linear regressors with data exhibiting power-law spectra ($\lambda_i \sim i^{-\alpha}$), the squared $\ell_2$-norm of the parameters grows as $\mathbb{E}[\|{\boldsymbol{\beta}}\|_{2}^{2}] = \Omega(n^{\alpha})$, where $n$ is the number of samples.
  • Exact Trade-off Formula: An explicit formula is derived for the asymptotic test error ($E_{test}$) as a function of the training error ($E_{train}$) and the data's eigenvalue decay exponent ($\alpha$). This formula shows that larger $\alpha$ leads to a worse trade-off.
  • Empirical Confirmation: Experiments with ridge regression and shallow neural networks on synthetic and real-world datasets align with the theoretical predictions, showing that faster eigenvalue decay (larger $\alpha$) indeed leads to poorer interpolation-generalization trade-offs.

Limitations and Future Work

  • Random Matrix Model: The theoretical results are derived under specific random matrix assumptions. Extending these findings to more general data distributions and models is a key future direction.
  • Uniform Convergence Bounds: The paper shows that existing norm-based bounds are loose for near-interpolators. A significant open question is whether data-dependent or uniform convergence-based approaches can yield non-vacuous generalization bounds for these scenarios.
  • Neural Networks: While empirical evidence suggests similar phenomena in neural networks, a rigorous theoretical understanding of norm growth and trade-offs in the neural network setting remains an open problem.
  • Early Stopping: The connection between early stopping (a practical technique for achieving near-interpolation) and the theoretical framework needs further exploration.

Summary updated

Abstract

We study the generalization capability of nearly-interpolating linear regressors: $\boldsymbol{\beta}$'s whose training error $\tau$ is positive but small, i.e., below the noise floor. Under a random matrix theoretic assumption on the data distribution and an eigendecay assumption on the data covariance matrix $\boldsymbol{\Sigma}$, we demonstrate that any near-interpolator exhibits rapid norm growth: for $\tau$ fixed, $\boldsymbol{\beta}$ has squared $\ell_2$-norm $\mathbb{E}[\|{\boldsymbol{\beta}}\|_{2}^{2}] = \Omega(n^{\alpha})$ where $n$ is the number of samples and $\alpha >1$ is the exponent of the eigendecay, i.e., $\lambda_i(\boldsymbol{\Sigma}) \sim i^{-\alpha}$. This implies that existing data-independent norm-based bounds are necessarily loose. On the other hand, in the same regime we precisely characterize the asymptotic trade-off between interpolation and generalization. Our characterization reveals that larger norm scaling exponents $\alpha$ correspond to worse trade-offs between interpolation and generalization. We verify empirically that a similar phenomenon holds for nearly-interpolating shallow neural networks.
BibTeX
@inproceedings{wang2024near,
  author = {Yutong Wang and Rishi Sonthalia and Wei Hu},
  title = {{Near-Interpolators: Rapid Norm Growth and the Trade-Off between Interpolation and Generalization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=wtJqDPk2p4},
}
Figure