Introduction
In the era of overparameterized neural networks, we have learned that models can "memorize" noisy labels without sacrificing test accuracy on clean data—a phenomenon widely known as benign overfitting. However, this paper proves that this overfitting is far from benign: interpolating label noise mathematically guarantees adversarial vulnerability.
Modern machine learning models are often large enough to achieve zero training error, even when the training data contains incorrect labels. While this might not hurt a model's standard accuracy, it raises a massive security concern regarding adversarial robustness. An adversarially vulnerable model might be 99% accurate but can be easily "tricked" into making a wrong prediction by a tiny, invisible perturbation to the input. This paper seeks to bridge the gap between label noise and robustness, asking: If a model is forced to perfectly fit (interpolate) noisy data, does it have to become vulnerable to adversarial attacks?
Moving beyond previous attempts that relied on narrow assumptions about data distribution, the authors provide a universal "law" relating noise to risk, demonstrating that purely random label noise is nearly as damaging as a deliberate poisoning attack.
Theoretical Framework & Methods
The authors combine rigorous mathematical proofs with empirical experiments to map out the "Law of Adversarial Risk."
- The Universal Bound (Theorem 2): The authors derive a new theorem using covering numbers (a measure of how "spread out" a dataset is). Unlike previous work, this theorem applies to any compactly supported data distribution and any interpolating classifier, regardless of the training algorithm. It establishes that for any interpolating classifier, the adversarial risk is lower-bounded by a constant (1/4) of the mass of the distribution, provided the sample size is large enough.
- Noise Model Comparison: They theoretically compare Uniform Label Noise (random flips) against Data Poisoning (where an adversary strategically picks which labels to flip).
- Inductive Bias Analysis: To explain why real-world models become vulnerable even with relatively small datasets, they investigate inductive bias—the inherent preference of a learning algorithm for certain types of solutions (e.g., "simple" or "smooth" functions).
- Memorization Scores: They use the concept of "atypicality" to measure which data points are being memorized and how that relates to the "long tail" of a distribution.
Empirical Evidence & Key Results
The paper validates its theory using standard benchmarks (MNIST, CIFAR-10, CIFAR-100) and noisy variants (CIFAR-10-n, CIFAR-100-n) containing real-world human annotator noise. They also utilize synthetic 1D, 2D, and 3D distributions to visualize decision boundaries.
The empirical results strongly support the theoretical claims. As label noise increases, adversarial risk skyrockets, even while training risk remains at zero (due to interpolation) and standard test risk remains relatively stable.
Key Insights
- The Inevitability of Vulnerability: If a dataset contains label noise and the model insists on zero training error, it must create "pockets" in its decision boundary to accommodate those noisy points. These pockets are the birthplaces of adversarial examples. Through 3D synthetic experiments, the authors demonstrate how models create "T-shaped" decision regions to "reach out" and grab noisy labels, inadvertently making nearby clean points vulnerable to perturbations.
- Uniform Noise is "Poison-Lite": The authors prove that random label noise is surprisingly effective at destroying robustness—almost as effective as a malicious attacker performing worst-case data poisoning.
- Human Error vs. Random Noise: Not all noise is created equal. Human errors tend to happen on "atypical" samples (the long tail of the distribution). Because these points are in low-density regions, the "pockets" created to memorize them don't affect the rest of the distribution as much. In contrast, uniform noise hits high-density regions, creating massive "vulnerability zones." On CIFAR-10, models interpolating human-generated noise were found to be significantly more robust than those interpolating the same amount of uniform random noise.
- The Inductive Bias Gap: There is a gap between what the general theorem predicts (requiring massive amounts of data to guarantee risk) and what we see in practice (high risk even with small datasets). The authors argue this is because neural networks have a "simplicity bias" that forces them to create larger-than-necessary vulnerability regions around noisy points.
Limitations and Future Work
While the universal theorem (Theorem 2) is mathematically "tight" (meaning a stronger universal law cannot be proven without specific architectural assumptions), it requires a sample size that scales exponentially with the data dimension. This doesn't fully explain why we see high adversarial risk in practice with much smaller datasets.
The authors conjecture that for specific architectures like neural networks, the sample size requirement is actually much lower (polynomial rather than exponential), though proving this remains an open challenge. Finally, while the paper highlights that inductive bias amplifies the effect of noise, future work is needed to precisely define which specific biases (e.g., those stemming from SGD or ReLU activations) are the primary culprits.
Summary updated