Failures of model-dependent generalization bounds for least-norm interpolation

Abstract

We consider bounds on the generalization performance of the least-norm linear regressor, in the over-parameterized regime where it can interpolate the data. We describe a sense in which any generalization bound of a type that is commonly proved in statistical learning theory must sometimes be very loose when applied to analyze the least-norm interpolant. In particular, for a variety of natural joint distributions on training examples, any valid generalization bound that depends only on the output of the learning algorithm, the number of training examples, and the confidence parameter, and that satisfies a mild condition (substantially weaker than monotonicity in sample size), must sometimes be very loose -- it can be bounded below by a constant when the true excess risk goes to zero.

References in corpus (8)

• Reconciling modern machine learning practice and the bias-variance trade-off
• Benign Overfitting in Linear Regression
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Uniform convergence may be unable to explain generalization in deep learning
• Does data interpolation contradict statistical optimality?
• Exact expressions for double descent and implicit regularization via surrogate random design
• Benign Overfitting and Noisy Features

Cited by in corpus (9)

• Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation
• A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning
• Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting
• When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?
• Exact Gap between Generalization Error and Uniform Convergence in Random Feature Models
• Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory
• When does gradient descent with logistic loss find interpolating two-layer networks?
• Generalization error of minimum weighted norm and kernel interpolation
• Classification and Adversarial examples in an Overparameterized Linear Model: A Signal Processing Perspective