Provable Tempered Overfitting of Minimal Nets and Typical Nets

Itamar Harel, William M. Hoza, Gal Vardi, Itay Evron, Nathan Srebro, Daniel Soudry

TL;DR

This paper provides the first theoretical proof of tempered overfitting in deep neural networks with binary weights, demonstrating that they can perfectly memorize noisy training data without suffering catastrophic generalization failure. Crucially, unlike previous theories that require extreme (very high or very low) input dimensions, these new bounds apply to deep architectures operating in realistic, moderate-dimensional regimes.

What Problem Does This Paper Address?

Modern neural networks are often heavily overparameterized, yet they generalize remarkably well even when trained to perfectly fit ("interpolate") noisy training data. Classical learning theory suggests that forcing a model to perfectly fit corrupted labels should lead to catastrophic overfitting. Recent empirical work has sought to understand this via a taxonomy of overfitting: benign (where generalization error approaches zero), tempered (where error is non-optimal but noticeably better than trivial guessing), and catastrophic.

While benign and tempered overfitting have been proven theoretically for linear models and kernel methods, these proofs typically require extreme input dimensions (e.g., the number of features must be vastly larger than the number of training samples). This left a significant gap in our understanding: can we mathematically prove tempered overfitting for deep, non-linear neural networks operating in moderate-dimensional regimes?

Methods

The authors tackle this problem by analyzing Binary Threshold Networks (BTNs)—fully connected deep neural networks with binary weights ($\{0,1\}$) and threshold activations. They study two distinct interpolation learning rules under a noisy "teacher" framework:

  1. Min-size interpolators: Networks whose layer widths are chosen to minimize the total number of weights needed to perfectly fit the data.
  2. Typical interpolators (posterior sampling): Networks sampled uniformly at random from the entire parameter space that perfectly fits the training set.

To prove their results, the authors introduce a novel technique from circuit complexity, showing that a constant-depth threshold network can memorize label noise using a sublinear number of parameters relative to the dataset size $N$. They use an XOR construction to cleanly separate the network's architecture into a component that mimics the clean teacher network and a small, efficient component that memorizes the noise. Finally, they apply information-theoretic mutual information bounds to derive the generalization limits.

Datasets

The paper is purely theoretical and does not evaluate on standard empirical benchmarks (like ImageNet or CIFAR). Instead, it utilizes a rigorous mathematical data model where binary feature vectors are sampled i.i.d. from a distribution, and labels are generated by a constant-size teacher network $h^*$ subjected to a controlled label-flipping noise rate $\epsilon^* < 0.5$.

Key Insights and Ideas

  • Tempered Overfitting is Provable in Deep Nets: The paper rigorously proves that deep networks don't just randomly guess when forced to memorize noise; their overfitting is bounded and "tempered"—worse than the Bayes-optimal error, but significantly better than a trivial classifier.
  • Occam's Razor for Noise: Min-size networks naturally limit their own complexity. Because memorizing noise requires a predictable information-theoretic minimum number of weights, a network minimizing its total size will allocate just enough resources to fit the noise without corrupting its underlying generalization capability.
  • The Surprising Regularization of "Typical" Networks: Even when a network is highly overparameterized, a randomly selected interpolating network ("typical net") generalizes almost as well as a min-size network. This happens because the vast majority of the valid parameter space naturally "freezes" redundant neurons to zero, implicitly regularizing the model without requiring explicit weight decay or gradient descent.

Key Results

  • For arbitrary label noise, the expected generalization error is bounded by $1 - 2^{-H(\epsilon^*)} + o(1)$, where $H$ is the binary entropy function.
  • For independent label noise, the generalization error concentrates tightly around $2\epsilon^*(1-\epsilon^*) + o(1)$. When evaluated against the clean distribution, this translates to a linear relationship with the noise level, closely matching empirical observations from prior literature.
  • These bounds hold for deep networks (depth $\ge 16$) under a moderate input dimension regime where the input dimension $d_0 = o(\sqrt{N/\log N})$.
Figure 1: Types of overfitting behaviors. Consider a binary classification problem of learning a realizable distribution D0. Let D be the distribution induced by adding an ε⋆-probability for a data point’s label to be flipped relative to D0. Suppose a model is trained with data from D. Then, assuming the classes are balanced, the trivial generalization performance is 0.5 (in gray; e.g., with a constant predictor). Left. Evaluating the model on D, a Bayes-optimal hypothesis (in red) obtains a generalization error of ε⋆. For large enough training sets, our results (Section 4) dictate a tempered overfitting behavior illustrated above. For arbitrary noise, the error is approximately bounded by 1−ε⋆ε⋆(1 −ε⋆)1−ε⋆(blue). For independent noise, the error is concentrated around the tighter 2ε⋆(1 −ε⋆) (yellow). A similar figure was previously shown in Manoj and Srebro [58] for shortest-program interpolators. Right. Assuming independent noise, the left figure can be transformed into the error of the model on D0 (see Lemma A.9). The linear behavior in the independent setting (yellow) is similar to the behavior observed empirically in Mallinar et al. [57, Figures 2, 3, and 6].

Limitations and Future Work

  • Specific Architecture: The proofs are tailored specifically to binary threshold networks. While the authors note that extensions to standard ReLU networks with continuous weights are possible, doing so currently yields much looser bounds.
  • Architectural Constraints: The mathematical proof requires a minimum network depth of 16 and a very large sublinear width ($\omega(N^{3/4})$), which does not perfectly mirror the shallower or more compact architectures often used in practice.
  • Interpolation Focus: The framework assumes perfect interpolation (zero training error) on consistent datasets, leaving open the question of how these bounds evolve under non-zero training thresholds or specific optimization trajectories like Stochastic Gradient Descent (SGD).

Summary updated

Abstract

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