When do Models Generalize? A Perspective from Data-Algorithm Compatibility
Authors:
- Jing XuJXJing Xu
- Jiaye TengJTJiaye Teng
- Yang YuanYYYang Yuan
- Andrew Chi-Chih YaoAYAndrew Chi-Chih Yao
Preprint
Abstract
One of the major open problems in machine learning theory is to characterize generalization in the overparameterized regime, where most traditional generalization bounds become inconsistent. 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 shortcoming, 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 fully exploits the algorithm information and therefore yields better generalization guarantees. We validate this by theoretically studying compatibility under the setting of overparameterized linear regression with gradient descent. Specifically, we perform a data-dependent trajectory analysis and derive a sufficient condition for compatibility under such a setting. Our theoretical results show that in the sense of compatibility, generalization holds with significantly weaker restrictions on the problem instance than the previous last iterate analysis.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Benign Overfitting and Noisy FeaturesJournal of the American Statistical Association, 2022
- Dimensionality Reduction, Regularization, and Generalization in Overparameterized RegressionsSIAM Journal on Mathematics of Data Science, 2022
- Information Complexity and Generalization Bounds2021
- The Generalization Error of Random Features Regression: Precise Asymptotics and the Double Descent CurveCommunications on Pure and Applied Mathematics, 2021
- Understanding deep learning (still) requires rethinking generalizationCommunications of the ACM, 2021
- Just interpolate: Kernel “Ridgeless” regression can generalizeThe Annals of Statistics, 2020
- Benign overfitting in linear regressionProceedings of the National Academy of Sciences, 2020
- Mastering the game of Go without human knowledgeNature, 2017
- The spectrum of kernel random matricesThe Annals of Statistics, 2010
- On Early Stopping in Gradient Descent LearningConstructive Approximation, 2007