Relaxing the Feature Covariance Assumption: Time-Variant Bounds for Benign Overfitting in Linear Regression

Jing Xu, Jiaye Teng, Andrew Chi-Chih Yao

Abstract

One of the major open problems in machine learning is to characterize generalization in the overparameterized regime, where most traditional generalization bounds become inconsistent (Nagarajan and Kolter, 2019). In many scenarios, their failure can be attributed to obscuring the crucial interplay between the training algorithm and the underlying data distribution. To address this issue, we propose a concept named compatibility, which quantitatively characterizes generalization in a both data-relevant and algorithm-relevant manner. By considering the entire training trajectory and focusing on early-stopping iterates, compatibility exploits the data and the algorithm information and is therefore a more suitable notion for generalization. We validate this by theoretically studying compatibility under the setting of solving overparameterized linear regression with gradient descent. Specifically, we perform a data-dependent trajectory analysis and derive a sufficient condition for compatibility in such a setting. Our theoretical results demonstrate that in the sense of compatibility, generalization holds with significantly weaker restrictions on the problem instance than the previous last iterate analysis.

Introduction: The Overparameterization Paradox

In modern machine learning, models often possess far more parameters than training examples. Classical statistical theory suggests these models should overfit by memorizing noise, yet they generalize remarkably well in practice. This "overparameterization paradox" has led to two main theoretical camps: those focusing on data structure (e.g., "benign overfitting") and those focusing on algorithmic bias (e.g., "stability").

However, these theories often fail to explain generalization in high-noise environments or the empirical success of early stopping. Traditional uniform convergence bounds frequently become mathematically inconsistent in these high-dimensional regimes. This paper introduces data-algorithm compatibility, arguing that generalization depends on the dynamic interplay between the data distribution and the entire training trajectory.

The Framework: Data-Algorithm Compatibility

Instead of analyzing only the "last iterate"—the model at the end of training—the authors propose looking at the entire path taken by Gradient Descent (GD). A data distribution and an algorithm are considered "compatible" if there exists a window of time during training where the model achieves near-zero excess risk as the sample size grows.

Time-Variant Bounds

The core of this framework is the derivation of time-variant generalization bounds. These bounds track how a model first learns useful features (reducing bias) before eventually fitting noise (increasing variance). By introducing refined effective dimensions ($k_0, k_1, k_2$) to measure the complexity of the data's covariance matrix, the authors can determine the relative speeds at which a model absorbs "signal" versus "noise."

Comparison of the proposed generalization bounds against existing literature for various eigenvalue distributions.

As shown in the theoretical comparison above, the proposed bounds outperform previous state-of-the-art results across several distribution types, including Inverse Polynomial and Constant distributions.

Empirical Validation

The theory was validated using both synthetic and real-world datasets:

  1. Synthetic Linear Regression: Datasets with specific eigenvalue spectra (Inverse Polynomial and Inverse Log-Polynomial) allowed for precise control over learning difficulty.
  2. Corrupted MNIST: Standard MNIST with 20% label noise was used to test the theory in a scenario where memorization is explicitly harmful.
Training trajectories for Linear Regression (left) and Corrupted MNIST (right), illustrating the "Goldilocks" zone where test error is minimized before noise memorization occurs.

The experimental results highlight a massive performance gap between the optimal early-stopped iterate and the final min-norm solution. On corrupted MNIST, the best iterate achieved a 2.88% test error, whereas the final iterate jumped to 19.9% as it began to fit the noise.

Key Insights

  • Generalization as a Joint Property: Generalization cannot be explained by data or algorithms in isolation; it is their interaction that defines the "Compatibility Region."
  • Signal vs. Noise Velocity: Models learn leading eigenvalues (signal) much faster than trailing ones (noise). Early stopping exploits this velocity difference.
  • Relaxing Assumptions: By accounting for the training trajectory, the strict conditions previously required for "benign overfitting" can be significantly weakened, suggesting more data types are learnable than previously thought.

Limitations and Future Work

While the theoretical proofs are currently limited to linear regression, the authors utilize the Neural Tangent Kernel (NTK) framework to bridge the gap toward deep learning. Future work aims to extend this trajectory analysis to non-linear architectures and non-convex optimization landscapes. Additionally, while the theory proves a compatibility region exists, identifying the optimal stopping point without a validation set remains a practical challenge.

Summary updated

Abstract

One of the major open problems in machine learning is to characterize generalization in the overparameterized regime, where most traditional generalization bounds become inconsistent (Nagarajan and Kolter, 2019). In many scenarios, their failure can be attributed to obscuring the crucial interplay between the training algorithm and the underlying data distribution. To address this issue, we propose a concept named compatibility, which quantitatively characterizes generalization in a both data-relevant and algorithm-relevant manner. By considering the entire training trajectory and focusing on early-stopping iterates, compatibility exploits the data and the algorithm information and is therefore a more suitable notion for generalization. We validate this by theoretically studying compatibility under the setting of solving overparameterized linear regression with gradient descent. Specifically, we perform a data-dependent trajectory analysis and derive a sufficient condition for compatibility in such a setting. Our theoretical results demonstrate that in the sense of compatibility, generalization holds with significantly weaker restrictions on the problem instance than the previous last iterate analysis.
BibTeX
@inproceedings{xu2023relaxing,
  author = {Jing Xu and Jiaye Teng and Andrew Chi-Chih Yao},
  title = {{Relaxing the Feature Covariance Assumption: Time-Variant Bounds for Benign Overfitting in Linear Regression}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=966yOmwk6d},
}
Figure