Towards Data-Algorithm Dependent Generalization: a Case Study on Overparameterized Linear Regression
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 52 of its 77 references that are in the map. First posted on arXiv 12 Feb 2022.
Builds on
52 of 77 references.
References · 52
- 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
- 2020Language Models are Few-Shot Learnerscited by 32,419
- 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
- 2017Spectrally-normalized margin bounds for neural networkscited by 686
- 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
- 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
- 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
- 2019Benign Overfitting in Linear Regressioncited by 549
- 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 533
- 2019Fantastic Generalization Measures and Where to Find Themcited by 513
- 2020The Pitfalls of Simplicity Bias in Neural Networkscited by 351
- 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 320
38 more
- 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 314
- 2018Stronger generalization bounds for deep nets via a compression approachcited by 307
- 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 303
- 2017High-dimensional dynamics of generalization error in neural networkscited by 241
- 2019Uniform convergence may be unable to explain generalization in deep learningcited by 224
- 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
- 2019Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networkscited by 159
- 2020Benign overfitting in ridge regressioncited by 153
- 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 119
- 2021Re-labeling ImageNet: from Single to Multi-Labels, from Global to Localized Labelscited by 118
- 2021Understanding and Improving Early Stopping for Learning with Noisy Labelscited by 113
- 2019Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setupcited by 112
- 2020Tighter risk certificates for neural networkscited by 112
- 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 98
- 2019Sharper bounds for uniformly stable algorithmscited by 93
- 2013Early stopping and non-parametric regression: An optimal data-dependent stopping rulecited by 89
- 2021Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Biascited by 83
- 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
- 2022Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Datacited by 74
- 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
- 2018Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passescited by 69
- 2018A Continuous-Time View of Early Stopping for Least Squarescited by 69
- 2020PAC-Bayes Analysis Beyond the Usual Boundscited by 63
- 2020The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networkscited by 58
- 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
- 2018Generalization Bounds for Uniformly Stable Algorithmscited by 56
- 2019In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictorscited by 44
- 2013A PAC-Bayesian Tutorial with A Dropout Boundcited by 43
- 2021Early-stopped neural networks are consistentcited by 34
- 2021Implicit Sparse Regularization: The Impact of Depth and Early Stoppingcited by 30
- 2020Generalization Error of Generalized Linear Models in High Dimensionscited by 25
- 2020On Uniform Convergence and Low-Norm Interpolation Learningcited by 24
- 2020The Statistical Complexity of Early-Stopped Mirror Descentcited by 19
- 2020Benign Overfitting and Noisy Featurescited by 18
- 2021Information Complexity and Generalization Boundscited by 14
- 2021Disparity Between Batches as a Signal for Early Stoppingcited by 9
- 2016Convergence rates of Kernel Conjugate Gradient for random design regressioncited by 8
- 2022Kernel Methods and Multi-layer Perceptrons Learn Linear Models in High Dimensionscited by 8
50 most cited of 52 All 52 (JSON)
Built on by
Citing papers per year: 2024: 1; 2025: 2.
3 papers.