mlsanityData to 14 Oct 2026

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

arXiv 2010.08479 ↗First posted 16 Oct 2020stat.ML cs.LG math.STcited by 26

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 26 papers in the map (data through 14 Oct 2026). First posted on arXiv 16 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 9; 2022: 7; 2023: 5; 2024: 3; 2025: 2.

26 papers.

Sort:

  1. 2021Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolationcited by 132
  2. 2021A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learningcited by 57
  3. 2021Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfittingcited by 54
  4. 2021Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolationcited by 42
  5. 2022The Implicit Bias of Benign Overfittingcited by 38
  6. 2023Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximizationcited by 29
  7. 2021Generalization Bounds using Lower Tail Exponents in Stochastic Optimizerscited by 27
  8. 2022Benign Underfitting of Stochastic Gradient Descentcited by 19
  9. 2023Fantastic Generalization Measures are Nowhere to be Foundcited by 19
  10. 2021Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regressioncited by 17
  11. 2023From Tempered to Benign Overfitting in ReLU Neural Networkscited by 16
  12. 2021Exact Gap between Generalization Error and Uniform Convergence in Random Feature Modelscited by 13
14 more
  1. 2022Instance-Dependent Generalization Bounds via Optimal Transportcited by 13
  2. 2022Small Transformers Compute Universal Metric Embeddingscited by 12
  3. 2023Noisy Interpolation Learning with Shallow Univariate ReLU Networkscited by 11
  4. 2022Deep Linear Networks can Benignly Overfit when Shallow Ones Docited by 8
  5. 2024Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionalitycited by 7
  6. 2022Max-Margin Works while Large Margin Fails: Generalization without Uniform Convergencecited by 6
  7. 2024Provable Tempered Overfitting of Minimal Nets and Typical Netscited by 5
  8. 2021Generalization Performance of Empirical Risk Minimization on Over-parameterized Deep ReLU Netscited by 4
  9. 2023Reinterpreting causal discovery as the task of predicting unobserved joint statisticscited by 4
  10. 2022Benign overfitting and adaptive nonparametric regressioncited by 3
  11. 2025Learning from one graph: transductive learning guarantees via the geometry of small random worldscited by 3
  12. 2025Transfer Learning for Benign Overfitting in High-Dimensional Linear Regressioncited by 3
  13. 2021Classification and Adversarial examples in an Overparameterized Linear Model: A Signal Processing Perspectivecited by 1
  14. 2024Which Algorithms Have Tight Generalization Bounds?cited by 1