# Provable Tempered Overfitting of Minimal Nets and Typical Nets

arXiv: https://arxiv.org/abs/2410.19092 · HTML: https://mlsanity.com/paper/2410.19092/

## Key facts

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

## Builds on (most cited first, 30 of 37)

- [On the Spectral Bias of Neural Networks](https://mlsanity.com/paper/1806.08734/) (2018)
- [Deep learning generalizes because the parameter-function map is biased towards simple functions](https://mlsanity.com/paper/1805.08522/) (2018)
- [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020)
- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data](https://mlsanity.com/paper/2202.05928/) (2022)
- [Is SGD a Bayesian sampler? Well, almost](https://mlsanity.com/paper/2006.15191/) (2020)
- [In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictors](https://mlsanity.com/paper/1912.04265/) (2019)
- [Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation](https://mlsanity.com/paper/2106.10865/) (2021)
- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)
- [The Implicit Bias of Benign Overfitting](https://mlsanity.com/paper/2201.11489/) (2022)
- [Benign Overfitting for Two-layer ReLU Convolutional Neural Networks](https://mlsanity.com/paper/2303.04145/) (2023)
- [Benign Overfitting and Grokking in ReLU Networks for XOR Cluster Data](https://mlsanity.com/paper/2310.02541/) (2023)
- [Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View](https://mlsanity.com/paper/2011.07729/) (2020)
- [Generalization Ability of Wide Neural Networks on ℝ](https://mlsanity.com/paper/2302.05933/) (2023)
- [Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization](https://mlsanity.com/paper/2303.01462/) (2023)
- [The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime](https://mlsanity.com/paper/1911.01544/) (2019)
- [Generalization in Kernel Regression Under Realistic Assumptions](https://mlsanity.com/paper/2312.15995/) (2023)
- [Failures of model-dependent generalization bounds for least-norm interpolation](https://mlsanity.com/paper/2010.08479/) (2020)
- [Interpolating Classifiers Make Few Mistakes](https://mlsanity.com/paper/2101.11815/) (2021)
- [Exponentially vanishing sub-optimal local minima in multilayer neural networks](https://mlsanity.com/paper/1702.05777/) (2017)
- [The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networks](https://mlsanity.com/paper/2108.11489/) (2021)
- [How Uniform Random Weights Induce Non-uniform Bias: Typical Interpolating Neural Networks Generalize with Narrow Teachers](https://mlsanity.com/paper/2402.06323/) (2024)
- [Tight bounds for minimum l1-norm interpolation of noisy data](https://mlsanity.com/paper/2111.05987/) (2021)
- [From Tempered to Benign Overfitting in ReLU Neural Networks](https://mlsanity.com/paper/2305.15141/) (2023)
- [An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks](https://mlsanity.com/paper/2106.07724/) (2021)
- [Harmless interpolation in regression and classification with structured features](https://mlsanity.com/paper/2111.05198/) (2021)
- [Memory capacity of neural networks with threshold and ReLU activations](https://mlsanity.com/paper/2001.06938/) (2020)
- [A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/2210.12082/) (2022)
- [Noisy Interpolation Learning with Shallow Univariate ReLU Networks](https://mlsanity.com/paper/2307.15396/) (2023)
- [Benign Overfitting in Two-Layer ReLU Convolutional Neural Networks for XOR Data](https://mlsanity.com/paper/2310.01975/) (2023)

## Built on by (most cited first, 5 of 5)

- [Beyond Benign Overfitting in Nadaraya-Watson Interpolators](https://mlsanity.com/paper/2502.07480/) (2025)
- [Quantifying Overfitting along the Regularization Path for Two-Part-Code MDL in Supervised Classification](https://mlsanity.com/paper/2503.02110/) (2025)
- [Harmful Overfitting in Sobolev Spaces](https://mlsanity.com/paper/2602.00825/) (2026)
- [Revisiting the Volume Hypothesis](https://mlsanity.com/paper/2606.31282/) (2026)
- [All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimension](https://mlsanity.com/paper/2602.08350/) (2026)

## 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.