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

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

TL;DR

This paper introduces data-algorithm compatibility, a new framework for understanding how overparameterized models generalize by analyzing the entire training trajectory rather than just the final result. By studying linear regression through this lens, the authors prove that early stopping allows for generalization under much broader conditions than previously thought, offering a theoretical explanation for why models that "overfit" to noise can still perform well if stopped at the right time.

What Problem Does This Paper Address?

In modern machine learning, we often use "overparameterized" models—models with far more parameters than training data points. Traditional statistical learning theory suggests these models should overfit and fail to generalize, yet in practice, deep neural networks generalize remarkably well.

Existing theories like "uniform convergence" often fail to explain this, providing bounds that are vacuous or inconsistent in overparameterized regimes. A more recent concept, benign overfitting, explains how the "last iterate" (the final solution that perfectly fits the training data) can still generalize. However, benign overfitting requires very specific, strict conditions on the data distribution. The authors argue that focusing only on the final solution ignores the crucial role of the training algorithm's path and the common practice of early stopping.

Methods

The authors shift the focus from the final solution to the training trajectory. They introduce the formal definition of data-algorithm compatibility: a data distribution and a training algorithm are compatible if there exists some point along the training path where the model's error (excess risk) vanishes as the sample size grows to infinity.

To validate this, they perform a deep dive into overparameterized linear regression trained with Gradient Descent (GD). Their technical approach involves:

  • Data-Dependent Trajectory Analysis: Deriving time-variant generalization bounds that track how error changes at every step of training.
  • Refined Bias-Variance Decomposition: Splitting the error into a bias term (how well the model fits the true signal) and a variance term (how much it fits the noise), showing how these evolve differently over time.
  • Effective Dimension Analysis: Using new notions of "effective rank" to characterize how the spectrum of the data covariance matrix interacts with the gradient descent dynamics.

Datasets

The paper uses two primary setups for evaluation:

  1. Synthetic Overparameterized Linear Regression: Features are sampled from Gaussian distributions with various covariance spectra (e.g., Inverse Polynomial, Inverse Log-Polynomial, Piecewise Constant) to test theoretical bounds.
  2. Corrupted MNIST: A classification task using a standard four-layer convolutional neural network (CNN) on the MNIST dataset, where 20% of the training labels are randomly shuffled (label noise) to simulate real-world data imperfections.

Key Insights and Ideas

  • Trajectory vs. Destination: Generalization is a property of the process, not just the end state. A model might be "compatible" with a dataset even if its final, fully-trained version is not "benign."
  • Early Stopping as a Generalization Engine: The authors show that models often learn useful features early in training and only start fitting noise much later. Early stopping isn't just a trick to save time; it's a fundamental mechanism that allows generalization in regimes where the final interpolating solution would fail.
  • Weaker Requirements: Compatibility holds under significantly milder assumptions than benign overfitting. For example, if the data spectrum decays very quickly, the final solution might fail to generalize (overfitting to noise), but an early-stopped solution can still be highly accurate.
The training plots show that while training loss continues to drop, excess risk/test error reaches a minimum early on and then rises as the model fits noise.

Key Results

  • Tighter Theoretical Bounds: The authors derived new bounds that outperform previous state-of-the-art results for several common data distributions. As shown in their comparison table, their bounds are often consistent ($o(1)$) in cases where previous "last-iterate" bounds were not.
Table 1: Comparison of excess risk bounds, showing the authors' method provides tighter results across various distributions.
  • Massive Empirical Gaps: In linear regression experiments, the generalization error of the final iterate was sometimes 100x larger than that of the optimal early-stopped solution.
  • Robustness to Noise: On corrupted MNIST, the best iterate on the trajectory achieved a 2.88% test error, while the final iterate (which fit the noisy labels) ballooned to 19.9%.

Limitations and Future Work

The primary limitation is that the rigorous theoretical proofs are currently confined to the linear regression setting. While the authors provide empirical evidence on CNNs and MNIST to show the intuition holds, extending the formal "compatibility" proofs to non-linear deep networks remains a major challenge.

Future work could involve applying this trajectory-based analysis to more complex architectures and exploring how different optimizers (like Adam or Sharpness-Aware Minimization) affect the compatibility region. The authors hope this work motivates a broader shift toward data-algorithm dependent trajectory analysis in machine learning theory.

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 Yang Yuan and Andrew Chi-Chih Yao},
  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