The fundamental trade-off between invariance and sensitivity of classification models to adversarial perturbations

1. 01What problem does this paper attempt to solve?

   The authors study the fundamental trade-off between sensitivity-based and invariance-based adversarial examples, arguing that defenses against the former exacerbate the latter.

   Core question: Does robustness optimization against sensitivity-based adversarial examples instead exacerbate the model's vulnerability to invariance-based adversarial examples?

   • Problem scenario: Sensitivity-based adversarial examples add a semantically small perturbation to the input to change the model output; invariance-based adversarial examples (Jacobsen et al., 2019) are the opposite—the perturbation changes the true label of the input while keeping the model prediction unchanged (Figure 1 gives an example of changing an MNIST 3 into a 5 with 20 pixels while the model still predicts 3).
   • Shortcomings of existing methods (according to the authors): The authors consider the lp norm a crude approximation of visual similarity, and that optimizing robustness around lp balls (Madry et al., 2017, etc.) is not only insufficient to resist general adversarial examples but may be harmful—the model becomes overly invariant to the true semantics of the task.
   • Core observation: When the formal robustness notion (lp ball) is misaligned with the task's perceptual metric (distance-oracle misalignment, Definition 3), low robust error against ε-bounded perturbations cannot simultaneously prevent both attack types, and improving sensitivity robustness reduces invariance robustness (Figure 2).
   • The paper proposes: A new algorithm for generating lp-bounded invariance adversarial examples; attacks on adversarially-trained and certifiably-robust models on MNIST; and a theoretical model attributing over-sensitivity and over-invariance to non-robust features and overly-robust features, respectively.
   • Threat model:
     • Attacker goal: Perturb input x within an ε norm bound so that the oracle label changes (O(x*)≠O(x) and not a garbage class) while the model prediction is unchanged (f(x*)=f(x)), i.e., Definition 2.
     • Knowledge: Model-agnostic—the attack generation does not access the model, and the same batch of samples is used to evaluate all models.
     • Capability: Apply l0 or l∞ (ε=0.3, 0.4) bounded perturbations to MNIST test images; success is determined by an ensemble of human evaluators (70% threshold).
     • Victim systems: Undefended, adversarially-trained, and certifiably-robust classifiers on MNIST.

   Collapse this answer

2. 02What related research exists?

   Related work falls into four groups: adversarial examples and sensitivity-based robustification, invariance failure modes, the feature perspective and criticism of lp norms, and attacked defense baselines.

   Adversarial examples and sensitivity robustness

   • Szegedy et al. (2013), Biggio et al. (2013)—proposed adversarial examples; Goodfellow et al. (2014, 2015) studied techniques to make classifiers robust to norm-bounded sensitivity attacks.
   • Madry et al. (2017), Wong & Kolter (2018), Raghunathan et al. (2018)—a series of defense proposals improving robustness under lp-ball constraints, which are among the targets of this paper's attacks.

   Invariance failure mode and feature perspective

   • Jacobsen et al. (2019)—defined invariance adversarial examples (unbounded perturbations that change the oracle label but preserve the classifier output); the authors note that Definition 2 in this paper is a deliberate restriction of it (changed to bounded perturbations, considering only the final classification).
   • Ilyas et al. (2019)—noted that over-sensitivity stems from non-robust but predictive features; the authors state this paper mirrors that observation, proposing that over-invariance stems from overly-robust features. Jo & Bengio (2017), Yin et al. (2019) are also cited as related.
   • Kaushik et al. (2019)—had annotators make minimal edits to change document semantics in NLP (counterfactually-augmented data), which the authors describe as a similar problem.

   Criticism of lp norms and perceptual misalignment

   • Sharif et al. (2018)—noted that l∞ noise of 25/255 can reliably fool human annotators on CIFAR-10.
   • Tsipras et al. (2019)—noted that perturbations on the order of 32/255 can effectively interpolate between CIFAR-10 classes; the authors believe their method may point to a way to automatically generate invariance attacks beyond MNIST.
   • Co et al. (2018)—showed that l∞ perturbations of 16/255 suffice to make an image of a cat look like a shower-curtain print.

   Baselines and attacked defenses

   • Models evaluated: l0-Sparse (Bafna et al., 2018), ABS and Binary-ABS (Schott et al., 2019), l∞-PGD and l2-PGD (Madry et al., 2017), undefended ResNet-18, and the certified defense of Zhang et al. (2019); benchmark is MNIST.
   • Authors' positioning: orthogonal to the study of feature-layer invariance by Engstrom et al. (2019a), Sabour et al. (2016), Jacobsen et al. (2019)—this paper studies invariance at the classification layer under bounded perturbations.

   Collapse this answer

3. 03How does the paper address this problem?

   The authors formalize the two types of adversarial examples and distance-oracle misalignment, propose a model-agnostic invariance attack algorithm, and use human evaluation as the oracle to judge success.

   Overall approach: first formally define two complementary failure modes and prove that when the norm and the oracle are misaligned, a robust objective necessarily trades one off against the other; then propose a model-agnostic invariance attack algorithm, using human evaluators to simulate the oracle in judging attack success, and finally evaluate the agreement rate of each model with human-rated labels.

   Problem formalization

   • Two definitions: a sensitivity adversarial example (Definition 1) requires f(x*)≠f(x) and perturbation norm ≤ε; an invariance adversarial example (Definition 2) requires f(x*)=f(x), O(x*)≠O(x), not a garbage class, and perturbation ≤ε.
   • Robust error objective: L_ε(f) = E_{(x,y)∼ D}[max_|Δ|≤ε {f(x+Δ) ≠ y}], i.e., the worst-case error rate within the ε bound optimized by existing defenses (Equation 1).
   • Misalignment definition: Definition 3 defines distance-oracle misalignment—if there exist same-class points farther than different-class points, then distance and oracle are misaligned. Lemma 4 states that constructing a distance function aligned with the oracle is as hard as perfectly solving the classification task (proof in Appendix D).

   Attack algorithm (Algorithm 1)

   • GenInv meta-algorithm: for input x, take the set S of different-class samples from training set X, apply a known set T of semantics-preserving transformations (rotation, translation, etc.), and return the transformed sample closest to x under the lp metric used.
   • l0 instantiation (Appendix A): T includes rotation up to 20 degrees, translation up to 6 pixels (out of 28), shear up to 20%, scaling up to 50%; then compute ∆=|x−x*|>1/2, perform spectral clustering on ∆ and enumerate cluster subsets to obtain candidates, score and filter with the AC-GAN class-conditional likelihood, reducing l0 perturbation by 50% on average; additionally filter out the 20% least regular samples in X.
   • l∞ instantiation (Appendix A): build the same augmented training set, but search only over target labels that are empirically more convincing (e.g., 1 paired with 7 or 4), then apply an l∞-bounded perturbation by interpolating with the target sample; the authors state the l∞ attack is less effective than l0 and was not further optimized.

   Success criterion and human-evaluation protocol

   • Model-agnostic success criterion: an attack succeeds if and only if the ensemble of human evaluators agrees, at a rate above 70%, on a new label different from the original label, independent of any model.
   • Human-evaluation setup: 40 evaluators, each classifying 100 digits (half unmodified MNIST, half from l0 and l∞ attack samples); additionally, one author handcrafted 50 l0/l∞ samples using a pixel-level editor.
   • Model evaluation: report the agreement rate between model predictions and human-rated labels only on "successful" samples where human evaluation confirmed a label change (Table 2).

   Theoretical model and data augmentation

   • Overly-robust feature model (Section 5): in a binary task, the oracle label is determined by feature x1 (O(x)=sign(x1)), and data "cleaning" augments spurious correlations between noise features x2…x_{d+2} and the label; Lemma 6 states that a standard classifier has agreement ≥1−δ with humans but is vulnerable to l∞ perturbations of O(d^{-1/2}), and Lemma 7 states that there exists an overly-robust classifier using only x2 with 1−α/2 robust accuracy against l∞ noise at ε=0.99 but vulnerable to invariance attacks (proof in Appendix E).
   • Data augmentation experiment: during training, the attacker first applies small rotation and translation, then adds ε-bounded l∞ noise (training samples 10 spatial transformations, 40 PGD steps each taking the strongest; testing enumerates all transformations, 100 PGD steps each), testing whether enforcing true invariance can prevent over-invariance.

   Collapse this answer

4. 04What experiments did the paper conduct?

   On MNIST, 100 generated attack samples were judged by 40 human raters; the agreement rate between robust models and human raters was generally lower than that of the undefended model, and on manual samples the certified model reached only 12%.

   Experimental setup

   • Models evaluated: Undefended ResNet-18, l0-Sparse (Bafna et al., 2018), Binary-ABS and ABS (Schott et al., 2019), l∞-PGD (ε=0.3) and l2-PGD (ε=2) (Madry et al., 2017); also evaluated the pretrained certified model of Zhang et al. (2019), and self-trained l∞-PGD (ε∈[0,0.4]) and l1-PGD (ε∈[0,15]) models.
   • Dataset: MNIST; the authors explain MNIST was chosen because it is the only vision task where a strongly robust model can be trained within a nontrivial lp ball.
   • Attack samples: 100 inputs randomly drawn from the MNIST test set, generating l0 and l∞ (ε=0.3, 0.4) attack samples respectively; additionally 50 handcrafted samples.
   • Success criterion: 40 human evaluators, 70% agreement threshold; model evaluation only on successful samples where human evaluation confirmed a label change.
   • Control metric: Table 3 (Appendix C) reports standard robust accuracy of the same models under sensitivity attacks (l0 using PointwiseAttack repeated 10 times, ε=25; l∞ using 100-step PGD).
   • Training details (Appendix C): self-trained models use the Madry et al. architecture, trained with Adam for 10 epochs; l∞-PGD trained for 40 steps, l1 using Sparse l1-Descent Attack (99% sparsity).

   Main results

   Attack success rate (Table 1, 70% human-evaluation threshold): clean 0%; l0 55%; l∞ ε=0.3 automatic 21%, handcrafted 26%; l∞ ε=0.4 automatic 37%, handcrafted 88%.

   Model agreement rate with human evaluation (Table 2, only on successful samples; * indicates exceeding that defense's threat model):

   Swipe horizontally to read the table

   Model	Clean	l0	l∞ ε=0.3	l∞ ε=0.4
   Undefended	99%	80%	33%	51%
   l0-Sparse	99%	38%	19%*	27%*
   Binary-ABS	99%	47%	0%	8%
   ABS	99%	58%	14%	18%
   l∞-PGD (ε=0.3)	99%	56%*	0%	16%*
   l2-PGD (ε=2)	99%	27%*	5%*	19%*

   • The authors state that the more robust a model is to sensitivity attacks, the lower its agreement rate with human evaluation on invariance samples; all robust models are worse than the undefended ResNet-18.
   • The authors note that Binary-ABS claims 60% empirical robust accuracy under l∞ ε=0.4, but on the paper's samples satisfying that bound it disagrees with human ratings 92% of the time (agreement rate 8%).
   • The authors explain: models designed to reduce over-sensitivity to non-semantic features become over-invariant to semantically meaningful features.

   Breaking certified defenses

   • What was tested: the pretrained model of Zhang et al. (2019), which proves test accuracy of at least 87% under l∞ ε=0.4.
   • Results: on all 100 ε=0.4 samples the model agrees with the original test labels 96% of the time, but agrees with human-rated new labels only 63%; on the 50 handcrafted samples it disagrees with human ratings 88% of the time, with an agreement rate of only 12%.
   • Authors' interpretation: the proof is mathematically correct, but humans change classification for many such perturbations, so it does not truly deliver 87% robust accuracy.

   Robustness-invariance trade-off and data augmentation

   • Figure 6: the larger the l∞-PGD training ε within [0,0.4], the lower the model's agreement rate with human evaluation on l∞ invariance samples; l1-PGD models show the same trend on l0 attacks. The authors state that sensitivity robustness does not generalize beyond the training bound, but over-invariance does generalize (models trained at ε=0.2 remain more vulnerable than undefended to attacks at ε≥0.3).
   • Figure 7/8: when training with a composite attack of spatial transformations + l∞ noise, the larger ε is, the harder it is to remain robust simultaneously (Figure 7); data augmentation raises the model's agreement rate with human evaluation (Figure 8), but at large ε it is still worse than the undefended model. The authors state that data augmentation helps but is insufficient to resist both types of attack simultaneously.

   Other ablations and analyses

   • Average l0 perturbation of successful l0 samples is 25.9, median 25 (Section 4.2).
   • l∞ attacks always use the full ε=0.3 or 0.4 budget, with runtime similar to l0 (alignment amortized to several minutes per image).
   • Of the 100 clean images, 98 were unanimously labeled by all evaluators, and the other 2 had over 90% agreement.
   • Under l0 attacks, 34/100 were agreed to have the original label at the 70% threshold, and 18 cases reached no consensus.
   • Appendix Table 4/5: sensitivity robust accuracy of self-trained models rises monotonically with training ε (e.g., l∞-PGD trained at ε=0.4 reaches 90% against PGD ε=0.4).

   Collapse this answer

5. 05What are some points that can be further explored?

   The authors note that the attack was not optimized, that data augmentation is insufficient to cover both types of attack, and call for more principled selection of robustness bounds; experiments are conducted only on MNIST.

   Limitations and future directions noted by the authors

   • Attack pipeline not optimized: the alignment process of the l0 attack costs several minutes per image amortized, and the authors state that this process was not optimized and could be improved (Section 4.2); the l∞ attack is weaker, and the authors state that further optimization might help (Appendix A).
   • Data augmentation insufficient: the authors state that even data augmentation on true invariant features is insufficient to train a model that resists both sensitivity and invariance attacks (Section 5).
   • Tasks beyond MNIST: the authors state that complex vision tasks such as ImageNet are also affected by the same trade-off, but that it has not yet manifested because non-trivially robust models cannot be trained on these tasks (Section 4.3); they also suggest that the approach of Tsipras et al. (2019) may point to a way to automatically generate invariance attacks beyond MNIST.
   • Choice of robustness bounds: the authors state that the results highlight the need for a more principled choice of meaningful robustness bounds and for measuring robustness progress (Section 7); they also argue that targeting lp-bounded attacks may be inherently futile for resisting arbitrary adversarial examples (Section 6).

   Scope of experiments

   • Experiments were conducted only on MNIST; the models tested were 6 existing models plus the Zhang et al. (2019) certified model and a self-trained PGD model (Section 4, Appendix C).
   • The attack sample scale was 100 automatic samples per norm, plus 50 manual samples; human evaluation used 40 raters, each rating 100 images (Section 4.2).
   • On the defense side, only data augmentation was evaluated as a mitigation (Section 5, Figure 7/8).
   • The paper does not report the number of model queries required for attack generation (the attack is model-agnostic), nor does it report statistical measures of inter-rater agreement (only consensus counts under a 70% threshold).
   • The theoretical analysis is limited to a binary classification toy model (Section 5, Appendix E).

   Collapse this answer

6. 06Summarize the main content of the paper

   The authors propose and verify a fundamental trade-off between sensitivity and invariance adversarial examples: on MNIST, the more robust the model, the greater its disagreement with human ratings, and certified defenses are also broken.

   An attack paper on a fundamental trade-off in adversarial examples: the authors study invariance-based adversarial examples—perturbations that change the label as judged by humans while keeping the model prediction unchanged—and argue that this trades off against the mainstream sensitivity-based failure mode.

   • Problem addressed: When lp norms are misaligned with task-aware metrics, optimizing robustness around lp balls makes the model overly invariant to semantic changes; the authors argue that existing defenses cannot defend against both attack types simultaneously and must trade off.
   • Method highlights: Formal definitions of the two types of adversarial examples and of distance-oracle misalignment (Lemma 4 states that constructing an aligned distance function is as hard as perfect classification); a model-agnostic attack algorithm, GenInv, that finds the nearest neighbor among transformed training samples of a different class and refines the perturbation; 40 human evaluators serve as the oracle with a 70% threshold.
   • Main results: l0 attack success rate 55% (100 cases), manual l∞ ε=0.4 reaches 88% (50 cases); in Table 2, all robust models have a lower agreement rate with human judgments on successful samples than the undefended ResNet-18, and Binary-ABS is 0% on l∞ ε=0.3; the certified model of Zhang et al. (2019) has only 12% agreement with human judgments on manual samples, and the authors state that its 87% certified robust accuracy is not what it claims to be.
   • Trade-off and mechanism: Figure 6 shows that the larger the PGD training ε, the lower the human-judgment agreement rate; the authors use an overly-robust feature model to explain why excessive invariance can fit and generalize, and state that MNIST experiments confirm the existence of such features.
   • Authors' conclusion: The authors state that robust bounds need to be chosen more principledly; data augmentation helps but is insufficient to resist both attack types simultaneously; and they argue that MNIST is far from solved, and that complex vision tasks will face the same trade-off once strong robust models can be trained.

   Collapse this answer

Related papers