On Uniform Convergence and Low-Norm Interpolation Learning
arXiv:2006.05942
Abstract
We consider an underdetermined noisy linear regression model where the minimum-norm interpolating predictor is known to be consistent, and ask: can uniform convergence in a norm ball, or at least (following Nagarajan and Kolter) the subset of a norm ball that the algorithm selects on a typical input set, explain this success? We show that uniformly bounding the difference between empirical and population errors cannot show any learning in the norm ball, and cannot show consistency for any set, even one depending on the exact algorithm and distribution. But we argue we can explain the consistency of the minimal-norm interpolator with a slightly weaker, yet standard, notion: uniform convergence of zero-error predictors in a norm ball. We use this to bound the generalization error of low- (but not minimal-) norm interpolating predictors.
arXiv commentv3: No content changes to this final version, as published at NeurIPS 2020: https://proceedings.neurips.cc/paper/2020/hash/4cc5400e63624c44fadeda99f57588a6-Abstract.html
References in corpus (7)
- Benign Overfitting in Linear Regression
- The generalization error of random features regression: Precise asymptotics and double descent curve
- Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate
- Uniform convergence may be unable to explain generalization in deep learning
- The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
- Optimistic Rates for Learning with a Smooth Loss
- Assumptionless consistency of the Lasso
Cited by in corpus (4)
- A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning
- Exact Gap between Generalization Error and Uniform Convergence in Random Feature Models
- Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory
- RATT: Leveraging Unlabeled Data to Guarantee Generalization