@inproceedings{
harel2024provable,
title={Provable Tempered Overfitting of Minimal Nets and Typical Nets},
author={Itamar Harel and William M. Hoza and Gal Vardi and Itay Evron and Nathan Srebro and Daniel Soudry},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=QyR1dNDxRP}
}
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.
Provable Tempered Overfitting of Minimal Nets and Typical Nets
Itamar Harel William M. Hoza Gal Vardi Itay Evron Nathan Srebro Daniel Soudry