Towards Data-Algorithm Dependent Generalization: a Case Study on Overparameterized Linear Regression

Jing Xu, Jiaye Teng, Andrew Chi-Chih Yao, Yao, Andrew Chi-Chih

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 even for overparameterized linear regression. In many scenarios, this failure can be attributed to obscuring the crucial interplay between the training algorithm and the underlying data distribution. This paper demonstrates that the generalization behavior of overparameterized models should be analyzed in a both data-relevant and algorithm-relevant manner. To make a formal characterization, we introduce a notion called data-algorithm compatibility, which considers the generalization behavior of the entire data-dependent training trajectory, instead of traditional last-iterate analysis. We validate our claim by studying 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 if we take early stopping iterates into consideration, generalization can hold with significantly weaker restrictions on the problem instance than the previous last-iterate analysis.

Introduction

In classical statistics, a model with more parameters than data points is expected to overfit and generalize poorly. However, modern deep learning has challenged this intuition: massive neural networks often generalize remarkably well. Existing theories, such as uniform convergence bounds, often become "vacuous" (meaningless) in these regimes. While recent work on "benign overfitting" explains how models can generalize even when perfectly fitting noisy data, these theories typically focus on the "last iterate"—the final state of the model after training to completion.

This paper argues that focusing solely on the final state misses a critical aspect of modern machine learning: the training trajectory. In practice, early stopping is a standard technique. By shifting the focus from the final "interpolating" solution to the entire training path, the authors propose a new framework to understand generalization through the lens of data-algorithm compatibility.

Methodology: Data-Algorithm Compatibility

The authors define a data distribution and an algorithm as "compatible" if there exists a region in the training timeline where the model achieves low excess risk. This moves away from static analysis toward a data-dependent trajectory analysis.

The study focuses on overparameterized linear regression solved via Gradient Descent (GD). While simple, this setup serves as a standard laboratory for high-dimensional phenomena and is linked to deep learning through the Neural Tangent Kernel (NTK) framework. The authors derive a new generalization bound that decomposes risk into bias and variance terms that evolve over time. This allows for tracking how a model first learns useful features (reducing bias) before eventually fitting noise (increasing variance). To characterize the covariance of the data, they introduce refined notions of "effective dimension" ($k_1$ and $k_2$), showing these metrics better predict early-stopping performance than those used for last-iterate analysis.

Results and Discussion

The research utilizes both synthetic overparameterized data with varying eigenvalue spectra (e.g., Inverse Polynomial, Log-Polynomial) and empirical datasets like Corrupted MNIST (with 20% label noise).

Training trajectories for Linear Regression and Corrupted MNIST, showing the gap between early-stopped and final iterates.

The empirical results highlight a massive performance gap between early-stopped and final iterates. In synthetic linear regression experiments, the early-stopping solution achieved an excess risk of 0.214, while the min-norm (final) iterate exploded to 43.472—a difference of over 200x. Similarly, on MNIST with 20% noise, the best iterate on the trajectory achieved a 2.88% test error, whereas the final iterate resulted in a 19.9% test error.

Theoretically, the derived bounds are tighter than previous benchmarks. For instance, in the "Constant" spectrum case, the proposed bound is $O(n^{-1/2})$, outperforming the $O(n^{-\min\{\epsilon, 1/2\}})$ from prior work.

Comparison of excess risk bounds across different data distributions.

Conclusion

The concept of data-algorithm compatibility demonstrates that generalization is a property of the training path, not just the end point. Early stopping is not merely a heuristic but a theoretical necessity that allows for generalization under much broader conditions than traditional last-iterate theories like benign overfitting. While this study focuses on linear regression, it provides a foundational concept that could lead to better hyperparameter selection and early-stopping criteria based on data geometry in non-linear deep learning models.

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 even for overparameterized linear regression. In many scenarios, this failure can be attributed to obscuring the crucial interplay between the training algorithm and the underlying data distribution. This paper demonstrate that the generalization behavior of overparameterized model should be analyzed in a both data-relevant and algorithm-relevant manner. To make a formal characterization, We introduce a notion called data-algorithm compatibility, which considers the generalization behavior of the entire data-dependent training trajectory, instead of traditional last-iterate analysis. We validate our claim by studying 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 if we take early stopping iterates into consideration, generalization can hold with significantly weaker restrictions on the problem instance than the previous last-iterate analysis.
BibTeX
@inproceedings{xu2023towards,
  author = {Jing Xu and Jiaye Teng and Andrew Chi-Chih Yao and Yao, Andrew Chi-Chih},
  title = {{Towards Data-Algorithm Dependent Generalization: a Case Study on Overparameterized Linear Regression}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=966yOmwk6d},
}
Figure