Towards Data-Algorithm Dependent Generalization: a Case Study on Overparameterized Linear Regression
Preprint
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.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Benign Overfitting and Noisy FeaturesJournal of the American Statistical Association, 2022
- Disparity Between Batches as a Signal for Early Stopping2021
- High-dimensional dynamics of generalization error in neural networksNeural Networks, 2020
- Optimal rates for spectral algorithms with least-squares regression over Hilbert spacesApplied and Computational Harmonic Analysis, 2020
- ConvNets and ImageNet Beyond Accuracy: Understanding Mistakes and Uncovering Biases2018
- Mastering the game of Go without human knowledgeNature, 2017
- Early Stopping — But When?2012
- Early stopping for non-parametric regression: An optimal data-dependent stopping rule2011
- On Early Stopping in Gradient Descent LearningConstructive Approximation, 2007
- Simplified PAC-Bayesian Margin Bounds2003