Research map / Learning theory and algorithms / Kernels and regression theory
Provable Tempered Overfitting of Minimal Nets and Typical Nets
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that min-size and posterior-sampled random binary threshold networks of depth ≥16 exhibit tempered overfitting on noisy-teacher data, via a new circuit bound for memorizing label flips.
Problem
Understanding overfitting behavior (benign, tempered, or catastrophic) of deep fully connected neural networks with binary weights that interpolate noisy labels, for input dimensions that are neither very high nor very low.
Approach
A new bound on the number of weights of a constant-depth binary threshold network consistent with a partial function (memorizing label flips with roughly H(eps)·N weights), combined with an XOR construction with the teacher; this bound feeds information-theoretic generalization bounds for min-size and uniformly sampled (posterior) interpolators.
Key results
- Min-size interpolators under arbitrary label noise have expected generalization error at most 1 - 2^{-H(eps)} + o(1).
- Under independent label noise, min-size interpolators' expected error is 2eps(1-eps) + o(1).
- Posterior-sampled random interpolators achieve analogous bounds with O(n log(d_max+d_0)/N) error terms.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a min-size NN interpolator to fit the noisy training set | Binary threshold networks · Noisy teacher, arbitrary label noise | expected generalization error: ≤ 1 - 2^{-H\rb{\errorRate}} + o \rb{1} | Helped |
| Use a min-size NN interpolator to fit the noisy training set | Binary threshold networks · Noisy teacher, independent label noise | expected generalization error: 2\varepsilon^{\star} \left(1\! -\!\varepsilon^{\star}\right) + o \rb{1} | Helped |
| Use posterior sampling over interpolating networks | Binary threshold networks · Noisy teacher, arbitrary label noise | expected generalization error: ≤ 1 - 2^{ - H\rb{\errorRate}} + O \rb{\frac{n\rb{\underline{d}} \cdot \log \rb{\dimsmax + d_0}}{N}} | Helped |
| Use posterior sampling over interpolating networks | Binary threshold networks · Noisy teacher, independent label noise | expected generalization error: 2\varepsilon^{\star}\left(1\! -\!\varepsilon^{\star}\right) \pm O \rb{\sqrt{\frac{n\rb{\underline{d}} \cdot \log \rb{\di | Helped |
Surprising findings
- Highly overparameterized random interpolators still generalize tempered, not catastrophically, despite standard bounds failing.
Limitations
- Requires network depth at least 16 and width on the order of N^{3/4}, which may be impractical.
- Relies on consistent training sets and bounded input dimension d0 = o(sqrt(N/log N)).
- Results limited to binary weights and activations; extensions to other quantization need looser bounds.
Experimental setup
Metrics: expected generalization error bounds on population error
Builds on: Lupanov circuit bounds Chashkin partial function circuit bound information-theoretic generalization bounds hitting set generators
Closest papers by meaning
- Noisy Interpolation Learning with Shallow Univariate ReLU Networks (ICLR 2024 · similarity 0.89)
- Benign overfitting in leaky ReLU networks with moderate input dimension (NeurIPS 2024 · similarity 0.87)
- Benign Overfitting in Adversarial Training of Neural Networks (ICML 2024 · similarity 0.85)
- On the Clean Generalization and Robust Overfitting in Adversarial Training from Two Theoretical Views: Representation Complexity and Training Dynamics (ICML 2025 · similarity 0.85)
- On the Hardness of Training Deep Neural Networks Discretely (AAAI 2025 · similarity 0.85)
- Benign Overfitting in Single-Head Attention (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.