Abstract
Benign overfitting refers to a recently discovered intriguing phenomenon that over-parameterized neural networks, in many cases, can fit the training data perfectly but still generalize well, even when the training labels are corrupted by noise. This paper provides a theoretical proof that two-layer neural networks with non-smooth activation functions (like ReLU) can perfectly overfit noisy training data while still generalizing well to unseen data. Crucially, the authors move beyond the restrictive "lazy training" (Neural Tangent Kernel) regime, showing that weights can travel far from their initialization, which better reflects how neural networks are actually trained in practice.
Introduction
In classical machine learning theory, the bias-variance tradeoff suggests that a model with enough capacity to perfectly fit noisy training data—a state known as overfitting—will inevitably suffer from poor generalization on new data. However, modern deep learning has turned this intuition on its head. Large neural networks frequently achieve zero training loss on noisy datasets yet maintain high accuracy on test sets. This phenomenon, termed benign overfitting, represents a significant gap between empirical success and theoretical understanding.
While recent mathematical frameworks have begun to explain this behavior, they often rely on two simplifying assumptions that distance the theory from real-world practice: the use of smooth activation functions and the "lazy training" regime. In the lazy regime (often associated with the Neural Tangent Kernel), the network is so over-parameterized that its weights barely move from their random initialization, effectively allowing the network to be analyzed as a linear model. This paper bridges the gap by providing a theoretical guarantee of benign overfitting for non-smooth neural networks operating outside the lazy training regime.
Theoretical Framework and Methodology
The authors analyze the training dynamics of a two-layer neural network trained with full-batch gradient descent using a logistic loss function. The study focuses on non-smooth activation functions, specifically the Rectified Linear Unit (ReLU), which is the standard in modern architecture but poses significant analytical challenges.
Overcoming Non-Smoothness
Because ReLU is not differentiable at zero, standard mathematical techniques like Taylor approximations—which are central to previous proofs—cannot be applied. Furthermore, non-smooth functions introduce the "dying ReLU" problem, where neurons can become inactive during training, causing gradients to vanish and training to stall. To address these issues, the authors developed two primary innovations:
- Tracking Active Neurons: The researchers developed a fine-grained analysis to track the state of individual neurons throughout the training process. They mathematically prove that a sufficient number of neurons remain "active" (maintaining a non-zero gradient), ensuring that the network continues to learn until the training loss is minimized.
- Global Weight Analysis: Traditional proofs often rely on local, step-by-step weight updates. However, this approach yields weak bounds when applied to non-smooth functions. The authors introduced a "global" approach utilizing random matrix theory and anti-concentration inequalities. By analyzing the total difference between the current weights and the initial weights, they bypass the statistical dependencies that typically complicate non-smooth analysis.
Data Model
As a theoretical work, the paper utilizes a mathematical mixture model rather than empirical datasets. In this model, data points are generated around a true mean vector with high-dimensional noise. To simulate real-world noise and test the limits of overfitting, a fraction of the training labels are adversarially flipped (polluted).
Key Insights
Persistence of Active Neurons
A major contribution of this work is the guarantee that correctly labeled active neurons are never deactivated during gradient descent. This stability is crucial for ensuring that the optimization process can drive the empirical loss toward zero even in the presence of label noise.
Departure from Lazy Training
Under the logistic loss function, driving the training error to zero requires the network's weights to grow infinitely large. This explicitly demonstrates that the network operates far outside the lazy training regime, where weights are assumed to stay close to their starting values. This finding aligns the theory more closely with the actual behavior of deep learning models.
Mathematical Efficiency
By shifting from local to global weight analysis, the authors saved a factor of $\sqrt{n}$ in their mathematical bounds. This refinement is what allows the proof to reach near-optimal generalization results that were previously unattainable for non-smooth models.
Results and Generalization
The paper establishes several rigorous bounds regarding the performance of these networks:
- Perfect Interpolation: The authors prove that the network can achieve arbitrarily small empirical loss ($\epsilon \to 0$), perfectly fitting the training data despite adversarial label corruption.
- Minimax Optimal Generalization: Despite the perfect fit of noise, the generalization error is bounded by $\exp(-n\|\mu\|^4 / Cp)$, where $n$ is the number of samples, $\mu$ is the class separation, and $p$ is the dimensionality. This matches the theoretical information-theoretic limit, or the minimax lower bound.
- Accelerated Convergence: The refined analysis yields a convergence rate of $O(1/t)$, which is significantly faster than the $O(1/\sqrt{t})$ rates found in prior works that relied on smooth activations.
Limitations and Future Directions
While this work marks a significant step forward, it focuses on two-layer networks. Extending these global analysis techniques to deeper architectures remains a primary challenge for future research. Additionally, the current proofs rely on a specific well-separated mixture model and high input dimensionality ($p$) relative to the number of samples ($n$). Future work may focus on relaxing these assumptions to accommodate more general data distributions and more intuitive over-parameterization bounds based on total parameter count rather than input dimension.
Summary updated