Source-linked AI summary
Adversarial Robustness May Be at Odds With Simplicity
Preetum Nakkiran
TL;DR
Current models can be accurate under standard and random perturbations yet fail to achieve comparable adversarial robustness. The paper gives theoretical examples showing that simple classifier classes can exhibit this gap and a robustness–accuracy tradeoff. In some examples, robust classification is possible only with much greater classifier complexity.
Problem
Current models can achieve high accuracy under standard and random perturbations but have not achieved comparable accuracy against adversarial perturbations.
Source: §1 · p. 1Method
The paper constructs classification tasks and simple classifier families to examine whether classifier complexity can explain the robustness gap and tradeoff.
Source: §1 · pp. 2–3Results
The examples show that simple classifiers can have low standard and noise-robust loss but high adversarial loss, although robust classifiers exist and may be exponentially more complex.
Source: §1 · p. 3Takeaways & Limitations
The observed tradeoff may arise from the structure of current classifier classes rather than being inherent to the classification task.
Source: §1 · p. 2The hypotheses are coarse-grained and may overlap, and one construction relies on an average-case-hard function described as unlikely to occur in Nature.
Source: §1 · p. 2, §1.2 · p. 4
Abstract
from arXiv · showhide
Current techniques in machine learning are so far are unable to learn classifiers that are robust to adversarial perturbations. However, they are able to learn non-robust classifiers with very high accuracy, even in the presence of random perturbations. Towards explaining this gap, we highlight the hypothesis that $\textit{robust classification may require more complex classifiers (i.e. more capacity) than standard classification.}$ In this note, we show that this hypothesis is indeed possible, by giving several theoretical examples of classification tasks and sets of "simple" classifiers for which: (1) There exists a simple classifier with high standard accuracy, and also high accuracy under random $\ell_\infty$ noise. (2) Any simple classifier is not robust: it must have high adversarial loss with $\ell_\infty$ perturbations. (3) Robust classification is possible, but only with more complex classifiers (exponentially more complex, in some examples). Moreover, $\textit{there is a quantitative trade-off between robustness and standard accuracy among simple classifiers.}$ This suggests an alternate explanation of this phenomenon, which appears in practice: the tradeoff may occur not because the classification task inherently requires such a tradeoff (as in [Tsipras-Santurkar-Engstrom-Turner-Madry `18]), but because the structure of our current classifiers imposes such a tradeoff.
1 Introduction
The paper asks why classifiers can perform well under standard and random perturbations yet fail under adversarial ones, and why robustness appears to trade off with accuracy. It gives theoretical examples where restricting classifiers to a simple class can produce that gap even though robust classification is possible.
1 Introduction
- The paper notes that its hypotheses are coarse-grained and may overlap, and that one construction uses an average-case-hard function considered unlikely to occur in Nature.It suggests instead choosing a function hard for a bounded-size classifier class, such as neural networks of a specific size.Source: §1 · p. 2, §1.2 · p. 4
- Across the examples, simple classifiers achieve low standard and noise-robust loss but high adversarial loss, while a robust classifier exists outside the simple class.The authors show that robust classification may require exponentially greater complexity in some examples.Source: §1 · pp. 2–3
- Among simple classifiers, the paper establishes a quantitative tradeoff between robustness and accuracy.The authors suggest the tradeoff may reflect the structure of current classifier classes rather than an inherent property of the classification task.Source: §1 · p. 3
1.1 Related Work
- The related-work discussion distinguishes classifier complexity from sample and computational complexity, and presents the paper's theoretical examples as evidence that the tradeoff may occur only within restricted classifier classes.The authors describe these as the first theoretical examples demonstrating Hypothesis (C).Source: §1 · p. 2, §1.1 · p. 3
1.2 Overview of Our Constructions.
- In one construction, linear thresholds have adversarial loss at least Ω(1), while coordinate-wise rounding gives a classifier with adversarial loss at most exp(-Ω(n)).The linear classifier is robust to random ℓ∞ noise of order ε; the construction can also be extended so all input coordinates have the same marginal distribution.Source: §1.2 · p. 4
- In the linear-threshold subclass with weights in {0, 1}^n, larger support improves standard accuracy but increases vulnerability to adversarial perturbations.The paper states that this tradeoff has a quantitative characterization.Source: §1.2 · p. 4
- A second construction gives a dictator classifier with zero standard loss, while any classifier running in time ≤2^O(n) has adversarial loss at least 1.It is built from a function g that is average-case hard for nonuniform algorithms running in 2^O(n) time.Source: §1.2 · p. 4
2 Formal Constructions
The section gives two theoretical constructions showing how simple classifiers can perform well under standard and random-noise losses yet fail under adversarial perturbations, while more complex classifiers can be robust. The second construction makes this limitation depend on average-case hardness.
2 Formal Constructions
- The section formally states properties of Constructions 1 and 2, with proofs deferred to the Appendix.It defines standard, adversarial, and noise-robust loss functionals.Source: §2 · p. 5
2.1 Construction 1
- Construction 1 uses a distribution D1 and the family of linear classifiers fw(x) = sign(⟨w, x⟩).The label is sampled uniformly, and each input coordinate is sampled independently according to the construction.Source: §2.1 · p. 5
- Construction 1 gives a linear classifier exponentially small standard and noisy loss, while every linear classifier has adversarial loss at least Ωε(1); a nonlinear classifier achieves exponentially small adversarial loss.These guarantees hold for ε ∈ (0.01, 1).Source: §2.1 · p. 5
- For Construction 1, the restricted family with weights in {0, 1}^n has a stated quantitative tradeoff between standard loss and adversarial loss.The supplied theorem passage introduces the tradeoff but does not include its inequality.Source: §2.1 · p. 5
2.2 Construction 2
- Construction 2 uses an average-case-hard function g to define a distribution Dg,ε over inputs and labels.The construction samples z and coordinate-wise uniform vectors a and b, then encodes g(z) and z into paired coordinates of x.Source: §2.2 · p. 6
- For Construction 2, the specified simple classifier has zero standard loss and exponentially small noisy loss, while classifiers running in time s(n) − Θ(n) have adversarial loss at least δ; a classifier with zero adversarial loss exists.The guarantees apply when g is (s(n), δ(n))-average-case hard and ε ∈ (0, 1/8).Source: §2.2 · p. 6
- A random function g suffices with constant probability to be (2^O(n), 1/2 − 2^−Ω(n))-average-case hard.Construction 2 extends the introduction's presentation to inputs whose coordinates are all marginally uniform and admits a simple noise-robust classifier.Source: §2.2 · p. 6
A Proofs
The proofs establish the construction guarantees using concentration bounds and reductions to average-case hardness. They also explain how decoding or rounding can yield classifiers with low adversarial loss.
Construction 1 proof
- For Construction 1, Chernoff-Hoeffding bounds give the classifier f1(x) = sign(∑i xi) exponentially small standard and noisy losses.The proof uses E[yxi] = 0.01 and conditional independence of the coordinates given y.Source: A Proofs · p. 7
- For any linear classifier, the adversarial-success bound is expressed using the distribution of yxi and the margin threshold ε||w||1.The proof then invokes E[zi]||w||1 and ||w||1 ≥ ||w||2 to bound the success probability.Source: A Proofs · p. 7
- Rounding each input coordinate before summing reverses perturbations for ε < 1, giving the nonlinear classifier adversarial loss equal to f1's standard loss.The resulting adversarial loss is exponentially small.Source: A Proofs · p. 7
Construction 2 proof
- For Construction 2, the simple classifier's noisy-loss bound follows because a coordinate event occurs with probability zero when g(z) = 0 and at least Ω(1) when g(z) = 1.Source: A Proofs · p. 8
- An ε-bounded adversary can make α independent of z, so a classifier with adversarial loss below δ would give an s(n)-time algorithm for computing g with error below δ, contradicting its average-case hardness.The simulated perturbed inputs can be generated in O(n) time.Source: A Proofs · p. 8
- Decoding z from β remains possible under perturbations of size ε < 1/4, so decoding z and computing g(z) gives a classifier with zero adversarial loss.Source: A Proofs · p. 8