A law of adversarial risk, interpolation, and label noise

Daniel Paleka, Amartya Sanyal

Abstract

In supervised learning, it has been shown that label noise in the data can be interpolated without penalties on test accuracy. We show that interpolating label noise induces adversarial vulnerability, and prove the first theorem showing the relationship between label noise and adversarial risk for any data distribution. Our results are almost tight if we do not make any assumptions on the inductive bias of the learning algorithm. We then investigate how different components of this problem affect this result, including properties of the distribution. We also discuss non-uniform label noise distributions; and prove a new theorem showing uniform label noise induces nearly as large an adversarial risk as the worst poisoning with the same noise rate. Then, we provide theoretical and empirical evidence that uniform label noise is more harmful than typical real-world label noise. Finally, we show how inductive biases amplify the effect of label noise and argue the need for future work in this direction.

Introduction

In the era of overparameterized neural networks, we have learned that models can perfectly memorize a training set—even one with incorrect labels—and still perform well on new, clean data. This phenomenon, known as "benign overfitting," suggests that interpolation (fitting the data perfectly) is not necessarily at odds with generalization.

However, accuracy is not the only metric of interest. This research investigates the hidden security tax of benign overfitting. If a model is forced to memorize a "dog" image that is incorrectly labeled as a "cat," how does that affect the model's sensitivity to small, adversarial perturbations? We establish a fundamental law showing that interpolating label noise guarantees a high adversarial risk across any data distribution, demonstrating that the "smoothness" of neural networks actually amplifies this vulnerability.

Theoretical Framework and Methods

To move beyond empirical observations, we provide a rigorous theoretical framework for why label noise and interpolation inevitably lead to brittle models. Our approach employs high-dimensional geometry and statistical learning theory, specifically focusing on covering numbers—the minimum number of balls needed to cover a data distribution.

Figure 1: Geometric illustration of data points and the covering of a distribution's support.

We prove Theorem 2, a distribution-free result that provides a lower bound on adversarial risk for any interpolating classifier. This theorem implies that if you have enough data and insist on zero training error in the presence of noise, you cannot avoid adversarial vulnerability, regardless of model architecture. We also introduce a "T-shaped" classifier construction to illustrate how the inherent "smoothness" of neural networks (the tendency to generalize a prediction from a point to its surrounding neighborhood) makes a single noisy label much more damaging than it would be for a "dimpled" classifier that only changes its prediction in a tiny, isolated hole.

Empirical Validation

We validated our theoretical findings using standard computer vision benchmarks, including MNIST, CIFAR-10, and CIFAR-100. To understand the impact of different noise types, we compared Uniform Noise (random flips) against Human Noise (natural mistakes made by annotators using CIFAR-10-n and CIFAR-100-n).

Figure 2: Adversarial risk (Adv), training risk (Train), and test risk (Test) as a function of label noise (η) across different datasets and architectures.

As shown in Figure 2, while training risk remains at zero (indicating perfect interpolation), the adversarial risk climbs sharply as the label noise rate increases. This trend holds across various architectures (ResNet18, DenseNet121) and datasets.

Key Insights

  • Uniform Noise is "Efficient" Poisoning: We prove that random uniform noise is surprisingly harmful—nearly as effective at destroying robustness as a strategic "poisoning" adversary who chooses exactly which labels to flip to cause the most damage.
  • The "Long Tail" is a Safe Haven: Real-world human errors aren't random; they usually happen on "atypical" or "hard" examples in the long tail of a distribution. Experiments show that models trained on human-generated noise are significantly more robust than those trained on the same rate of uniform random noise. Memorizing these specific mistakes is less damaging to overall robustness than memorizing random noise in the "dense" parts of the data.
  • Smoothness as a Double-Edged Sword: While smoothness is generally desirable for generalization, when a model interpolates a noisy label, this smoothness forces a large "bubble" of the wrong class to appear around that point, creating a massive target for adversarial attacks.

Conclusion and Future Work

Our work establishes that the cost of interpolating label noise is a guaranteed increase in adversarial risk. While Theorem 2 provides a mathematical guarantee, the sample size required for it to "kick in" theoretically is much larger than what we observe in practice. This suggests that the inductive bias of neural networks is doing the heavy lifting in creating vulnerability.

Future research should focus on better mathematical proxies for "realistic" label noise, as uniform random noise is an overly pessimistic model. Additionally, we conjecture that for specific architectures like single-hidden-layer networks, the sample complexity for guaranteed risk is much lower (polynomial rather than exponential), a direction that warrants further investigation.

Summary updated

Abstract

In supervised learning, it has been shown that label noise in the data can be interpolated without penalties on test accuracy. We show that interpolating label noise induces adversarial vulnerability, and prove the first theorem showing the relationship between label noise and adversarial risk for any data distribution. Our results are almost tight if we do not make any assumptions on the inductive bias of the learning algorithm. We then investigate how different components of this problem affect this result, including properties of the distribution. We also discuss non-uniform label noise distributions; and prove a new theorem showing uniform label noise induces nearly as large an adversarial risk as the worst poisoning with the same noise rate. Then, we provide theoretical and empirical evidence that uniform label noise is more harmful than typical real-world label noise. Finally, we show how inductive biases amplify the effect of label noise and argue the need for future work in this direction.
BibTeX
@inproceedings{paleka2023law,
  author = {Daniel Paleka and Amartya Sanyal},
  title = {{A law of adversarial risk, interpolation, and label noise}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=0_TxFpAsEI},
}
Figure