Introduction
In adversarial machine learning, an adversarial example is defined as an input modified to fool a model while remaining perceptually identical to the original for a human observer. To automate the creation and defense of these examples, researchers have long relied on $L_p$-norms (e.g., $L_2$ Euclidean distance or $L_\infty$ maximum pixel change) as mathematical proxies for human vision. This paper challenges this foundational assumption, demonstrating through mathematical analysis and human user studies that $L_p$-norms are neither necessary nor sufficient to define perceptual similarity.
The Flaw of Necessity
A metric is a necessary condition for similarity if all perceptually similar images have a small distance under that metric. However, simple geometric transformations—such as rotating an image by a few degrees or shifting it by a few pixels—can result in massive $L_p$ distances, even though the image's content remains unchanged to a human observer.
As shown in Figure 1, a slightly rotated dog or horse is immediately recognizable to a human, yet the pixel-wise difference ($L_p$ distance) from the original is significant. This suggests that models defended only against $L_p$ perturbations remain vulnerable to simple, non-adversarial transformations that humans ignore.
The Flaw of Sufficiency
The core contribution of this work is proving that $L_p$-norms are also not sufficient to guarantee similarity. A small $L_p$ "budget" does not ensure that an image looks the same. The researchers conducted three online user studies with 399 participants to compare benign images ($C_B$) with two types of adversarial examples: those designed to be imperceptible ($C_{AI}$) and those crafted to be perceptible ($C_{AP}$) while staying within the same $L_p$ budget.
They found that an attacker can "spend" an $L_p$ budget to concentrate changes into recognizable features. For instance, a small $L_0$ budget can be used to change a '3' into an '8' in a way that is obvious to a human but mathematically "close" to the original '3'. If a human sees an '8' where the metric says it is a '3', the $L_p$ metric has failed as a proxy for perception.
Experimental Evidence
The user studies provided quantitative proof of $L_p$ failure across common datasets like MNIST and CIFAR-10, testing against robust models such as those proposed by Madry et al.:
- MNIST ($L_0$): Human accuracy on benign digits was 95%, but it plummeted to just 3% on perceptible adversarial examples ($C_{AP}$), despite the small $L_0$ distance. Participants were highly confident in their incorrect (relative to the original label) classifications.
- CIFAR-10 ($L_2$): At a distance of 6.0, human accuracy dropped from 93% to 57% for the perceptible group.
- CIFAR-10 ($L_\infty$): With a threshold of 0.1, human accuracy dropped from 91% to 36%.
Implications and Conclusion
The failure of $L_p$-norms has serious implications for the field. If adversarial training uses $L_p$ balls that include images humans would label differently, the model is effectively being trained on mislabeled data—a form of label poisoning.
Furthermore, the "invisibility" of many state-of-the-art attacks may be an artifact of the metric rather than a property of the attack itself. The authors conclude that the community must move beyond raw pixel differences and adopt more sophisticated perceptual metrics—such as SSIM or GMSD—or human-in-the-loop evaluations that account for geometric invariance and structural features.
Summary updated