mlsanityData to 7 Oct 2026

Provable Tempered Overfitting of Minimal Nets and Typical Nets

arXiv 2410.19092 ↗First posted 24 Oct 2024cs.LG stat.MLcited by 5

Not on the map. Why?

Abstract (arXiv)

We study the overfitting behavior of fully connected deep Neural Networks (NNs) with binary weights fitted to perfectly classify a noisy training set. We consider interpolation using both the smallest NN (having the minimal number of weights) and a random interpolating NN. For both learning rules, we prove overfitting is tempered. Our analysis rests on a new bound on the size of a threshold circuit consistent with a partial function. To the best of our knowledge, ours are the first theoretical results on benign or tempered overfitting that: (1) apply to deep NNs, and (2) do not require a very high or very low input dimension.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 37 of its 99 references that are in the map. First posted on arXiv 24 Oct 2024.

Builds on

37 of 99 references.

References · 37

  1. 2018On the Spectral Bias of Neural Networkscited by 1,321
  2. 2018Deep learning generalizes because the parameter-function map is biased towards simple functionscited by 180
  3. 2020Benign overfitting in ridge regressioncited by 152
  4. 2022Benign Overfitting in Two-layer Convolutional Neural Networkscited by 90
  5. 2022Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Datacited by 74
  6. 2020Is SGD a Bayesian sampler? Well, almostcited by 50
  7. 2019In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictorscited by 44
  8. 2021Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolationcited by 41
  9. 2021On the Optimal Memorization Power of ReLU Neural Networkscited by 40
  10. 2022The Implicit Bias of Benign Overfittingcited by 38
  11. 2023Benign Overfitting for Two-layer ReLU Convolutional Neural Networkscited by 34
  12. 2020Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic Viewcited by 32
25 more
  1. 2023Benign Overfitting and Grokking in ReLU Networks for XOR Cluster Datacited by 32
  2. 2023Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximizationcited by 29
  3. 2023Generalization Ability of Wide Neural Networks on ℝcited by 28
  4. 2019The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regimecited by 27
  5. 2020Failures of model-dependent generalization bounds for least-norm interpolationcited by 26
  6. 2023Generalization in Kernel Regression Under Realistic Assumptionscited by 26
  7. 2021Interpolating Classifiers Make Few Mistakescited by 22
  8. 2017Exponentially vanishing sub-optimal local minima in multilayer neural networkscited by 19
  9. 2021The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networkscited by 18
  10. 2024How Uniform Random Weights Induce Non-uniform Bias: Typical Interpolating Neural Networks Generalize with Narrow Teacherscited by 18
  11. 2021Tight bounds for minimum l1-norm interpolation of noisy datacited by 16
  12. 2023From Tempered to Benign Overfitting in ReLU Neural Networkscited by 16
  13. 2021An Exponential Improvement on the Memorization Capacity of Deep Threshold Networkscited by 14
  14. 2021Harmless interpolation in regression and classification with structured featurescited by 14
  15. 2020Memory capacity of neural networks with threshold and ReLU activationscited by 13
  16. 2022A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Modelscited by 11
  17. 2023Noisy Interpolation Learning with Shallow Univariate ReLU Networkscited by 11
  18. 2023Benign Overfitting in Two-Layer ReLU Convolutional Neural Networks for XOR Datacited by 10
  19. 2019On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernelscited by 7
  20. 2023Training shallow ReLU networks on noisy data using hinge loss: when do we overfit and is it benign?cited by 7
  21. 2020Overfitting Can Be Harmless for Basis Pursuit, But Only to a Degreecited by 5
  22. 2023Interpolation Learning With Minimum Description Lengthcited by 5
  23. 2023An Agnostic View on the Cost of Overfitting in (Kernel) Ridge Regressioncited by 5
  24. 2024Benign overfitting in leaky ReLU networks with moderate input dimensioncited by 5
  25. 2020On the robustness of the minimum ℓ2 interpolatorcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 2; 2026: 3.

5 papers.

  1. 2025Beyond Benign Overfitting in Nadaraya-Watson Interpolatorscited by 2
  2. 2025Quantifying Overfitting along the Regularization Path for Two-Part-Code MDL in Supervised Classificationcited by 2
  3. 2026Revisiting the Volume Hypothesiscited by 1
  4. 2026Harmful Overfitting in Sobolev Spacescited by 0
  5. 2026All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimensioncited by 0