---
title: Adversarial Robustness
module: Theory & Frontiers
moduleNumber: 6
lessonNumber: 2
order: 602
summary: >
  A trained network can be fooled by a perturbation too small for a human to see:
  add a carefully aimed vector of magnitude $\epsilon$ to a correctly classified
  image and the prediction flips. We derive the fast gradient sign method as the
  first-order-optimal step inside an $L_\infty$ ball, explain the linearity
  hypothesis that makes high-dimensional models so easy to push around, build up
  to projected gradient descent, and frame adversarial training as a min-max
  robust-optimization problem with its own accuracy cost. Defenses beyond training
  continue in the next lesson.
topics: [Theory & Frontiers]
sources:
  - book: Goodfellow
    ref: "§7.13 — Adversarial Training; Ch. 7 Regularization"
  - book: Goodfellow
    ref: "Goodfellow, Shlens & Szegedy (2015) — Explaining and Harnessing Adversarial Examples"
  - book: Chollet
    ref: "Ch. 5 — Fundamentals of ML (generalization, the manifold view)"
---

A network that hits human-level accuracy on a test set can still be steered to
any wrong answer you like by a perturbation you cannot see. Take a correctly
classified image $x$, add a vector $\delta$ with $\norm{\delta}_\infty \le
\epsilon$ for some tiny $\epsilon$ (a few gray levels out of $255$), and the
model's prediction flips with high confidence. The perturbed input $x' = x +
\delta$ is an **adversarial example**.[^gf-adv] This is not a rare glitch on a handful of
inputs; for an undefended deep network it is the generic situation, and it is the
sharpest known failure of the [flat decision boundaries](/deep-learning/foundations/linear-models-and-the-perceptron)
that linear readouts draw near the data.

> **Definition (Adversarial example).** Given a model $f_\theta$, a correctly
> classified input $x$ with label $y$, and a budget $\epsilon$, an adversarial
> example is a perturbed input $x' = x + \delta$ with $\norm{\delta}_p \le
> \epsilon$ such that $f_\theta(x') \ne y$. The perturbation $\delta$ is typically
> imperceptible: under the $L_\infty$ norm every pixel moves by at most $\epsilon$.

## The threat model

"Robust" is meaningless until we say _against what_. A threat model fixes three
things: the **perturbation set** the attacker may choose $\delta$ from, the
**knowledge** the attacker has of the model, and the **goal** of the attack. The
perturbation set is almost always a norm ball $\{\delta : \norm{\delta}_p \le
\epsilon\}$, and the two norms that dominate the literature carve out very
different shapes.

$$
% caption: The two perturbation sets around a clean input. The $L_\infty$ ball is a box (per-coordinate cap); the $L_2$ ball is a sphere (bounded energy).
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % --- L-infinity box ---
  \begin{scope}
    \draw[acc, very thick] (-1.3,-1.3) rectangle (1.3,1.3);
    \fill[black] (0,0) circle (2.2pt);
    \node[anchor=north, font=\footnotesize] at (0,-0.12) {clean};
    \node[acc, font=\footnotesize, anchor=south] at (0,1.35) {box: max per-pixel move};
    \draw[<->, black] (-1.3,-1.7) -- (1.3,-1.7);
    \node[black, font=\footnotesize, anchor=north] at (0,-1.72) {width $2\,$eps};
  \end{scope}
  % --- L2 ball ---
  \begin{scope}[xshift=6cm]
    \draw[green, very thick] (0,0) circle (1.3);
    \fill[black] (0,0) circle (2.2pt);
    \node[anchor=north, font=\footnotesize] at (0,-0.12) {clean};
    \node[green, font=\footnotesize, anchor=south] at (0,1.35) {ball: bounded total energy};
    \draw[<->, black] (0,0) -- (1.3,0);
    \node[black, font=\footnotesize, anchor=south] at (0.65,0.02) {radius eps};
  \end{scope}
\end{tikzpicture}
$$

| Axis | Choices | What it means |
| --- | --- | --- |
| Perturbation set | $L_\infty$ ball / $L_2$ ball / $L_0$ (few pixels) | the geometry of allowed $\delta$ |
| Knowledge | **white-box** (full $\theta$, gradients) / **black-box** (queries only) | what the attacker can compute |
| Goal | **untargeted** (any wrong class) / **targeted** (a chosen wrong class) | how hard the attack is |

> **Definition (Threat model).** A specification of the attacker's allowed
> perturbation set $\mathcal{S} = \{\delta : \norm{\delta}_p \le \epsilon\}$,
> their access to the model (white-box: exact gradients $\nabla_x \ell$; black-box:
> only input-output queries), and their objective (untargeted or targeted). Every
> robustness claim is a claim _relative to a fixed threat model_; none is absolute.

White-box is the worst case and the one robustness is measured against: assume the
attacker has $\theta$ and can differentiate through the model. A defense that only
survives black-box attackers is usually relying on the attacker not knowing the
gradient, a fragile assumption we return to under **gradient masking**.

## FGSM: the first-order-optimal $L_\infty$ step

The attacker wants to _increase_ the loss $\ell(x, y)$, pushing the model away
from the correct answer, while keeping $\delta$ inside the $L_\infty$ ball. Hold
$\theta$ and $y$ fixed and linearize the loss around $x$ with a first-order Taylor
expansion:

$$
\ell(x + \delta,\, y) \;\approx\; \ell(x, y) \;+\; \nabla_x \ell(x, y)^\top \delta.
$$

To maximize the loss we maximize the inner product $g^\top \delta$, writing $g =
\nabla_x \ell(x, y)$, subject to $\norm{\delta}_\infty \le \epsilon$. This is
a tiny constrained optimization with a closed form: each coordinate $\delta_j$ is
free in $[-\epsilon, \epsilon]$ and contributes $g_j \delta_j$, so the sum is
maximized by pushing each coordinate to its extreme _in the direction of its
gradient sign_.

$$
\max_{\norm{\delta}_\infty \le \epsilon} g^\top \delta
\;=\; \max_{\delta} \sum_{j} g_j \delta_j
\;=\; \sum_{j} \epsilon\,|g_j|
\;=\; \epsilon\,\norm{g}_1,
\qquad
\delta_j^\star = \epsilon\,\sign(g_j).
$$

That optimal $\delta^\star$ is the **fast gradient sign method** (FGSM).[^gf-fgsm] The
maximum achievable first-order loss increase is $\epsilon\norm{g}_1$; it scales
with the $L_1$ norm of the gradient, which grows with dimension.

The sign appears because the constraint is $L_\infty$, and the tightest bound on a
linear form under an $L_p$ constraint is Hölder's inequality,
$g^\top\delta \le \norm{g}_q\,\norm{\delta}_p$ with $1/p + 1/q = 1$. For $p=\infty$
the dual is $q=1$, giving the bound $\epsilon\norm{g}_1$, attained by
$\delta = \epsilon\,\sign(g)$. Change the constraint and the optimal
step changes with it: under an $L_2$ budget $\norm{\delta}_2 \le \epsilon$ the dual
is $q=2$, the bound is $\epsilon\norm{g}_2$, and the maximizer is the normalized
gradient $\delta^\star = \epsilon\,g/\norm{g}_2$ — ordinary steepest ascent.
Each norm ball selects the steepest-ascent direction _in its own geometry_: FGSM is
steepest ascent measured in $L_\infty$.

$$
% caption: The steepest-ascent step depends on the norm ball. Under the $L_\infty$ box the optimum is the sign vector reaching a corner; under the $L_2$ ball it is the normalized gradient, reaching the point where the ball is tangent to the loss level set.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % ===== LEFT: L-infinity =====
  \begin{scope}
    \node[font=\footnotesize, anchor=south, acc] at (0,1.7) {Linf box};
    \draw[acc, very thick] (-1.2,-1.2) rectangle (1.2,1.2);
    \fill[black] (0,0) circle (2.2pt);
    \draw[->, black, very thick] (0,0) -- (0.75,0.5);
    \node[font=\footnotesize, anchor=north west] at (0.72,0.5) {g};
    \draw[->, green, very thick, dashed] (0,0) -- (1.2,1.2);
    \fill[green] (1.2,1.2) circle (2.2pt);
    \node[green, font=\footnotesize, anchor=west] at (1.28,1.2) {sign step};
  \end{scope}
  % ===== RIGHT: L2 =====
  \begin{scope}[xshift=6cm]
    \node[font=\footnotesize, anchor=south, acc] at (0,1.7) {L2 ball};
    \draw[acc, very thick] (0,0) circle (1.2);
    \fill[black] (0,0) circle (2.2pt);
    \draw[->, black, very thick] (0,0) -- (0.72,0.48);
    \node[font=\footnotesize, anchor=north west] at (0.7,0.48) {g};
    \draw[->, green, very thick, dashed] (0,0) -- (1.0,0.665);
    \fill[green] (1.0,0.665) circle (2.2pt);
    \node[green, font=\footnotesize, anchor=west] at (1.24,0.7) {normalized};
  \end{scope}
\end{tikzpicture}
$$

For example, take a three-pixel input with
clean values $x = (0.50,\, 0.50,\, 0.50)$, and suppose the input-gradient of the
loss at $x$ is $g = (+0.8,\, -0.2,\, +0.4)$. With budget $\epsilon = 0.1$, FGSM sets
each coordinate to $x_j + \epsilon\,\sign(g_j)$:

$$
\delta = 0.1 \cdot \sign(0.8,\, -0.2,\, 0.4) = (+0.1,\, -0.1,\, +0.1),
\qquad
x' = (0.60,\, 0.40,\, 0.60).
$$

Every pixel moved by exactly $\epsilon$ regardless of the magnitude of its gradient
component — the sign discards magnitude and keeps only direction. The first-order
loss increase is $g^\top\delta = 0.08 + 0.02 + 0.04 = 0.14 = \epsilon\norm{g}_1$,
matching the bound. Had we instead used the raw gradient step
$x + \epsilon\,g = (0.58,\,0.48,\,0.54)$, the largest coordinate would have moved
only $0.08 < \epsilon$: it underuses the $L_\infty$ budget on the small-gradient
pixels. The sign is what saturates every coordinate to the box wall.

> **Definition (FGSM).** The fast gradient sign method takes one step of size
> $\epsilon$ in the sign of the input-gradient:
> $$
> x' = x + \epsilon\,\sign\!\parens{\nabla_x \ell(x, y)}.
> $$
> It is the exact maximizer of the first-order (linearized) loss over the $L_\infty$
> ball of radius $\epsilon$ — the steepest ascent step measured in the $L_\infty$
> norm, just as ordinary gradient ascent is steepest in $L_2$.

$$
% caption: FGSM geometrically. The sign step $\epsilon\,\mathrm{sign}(g)$ jumps to the corner of the $L_\infty$ box best aligned with the gradient $g$, crossing the boundary.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % the L-inf box around x
  \draw[black, thick] (-1.4,-1.4) rectangle (1.4,1.4);
  % decision boundary (curve crossing the box)
  \draw[red, very thick] (-2.0,-0.6) .. controls (-0.2,0.9) and (0.8,1.5) .. (2.2,2.4)
    node[anchor=west, font=\footnotesize, text=red] {boundary};
  % regions
  \node[green, font=\footnotesize] at (-1.7,1.7) {correct};
  \node[red, font=\footnotesize] at (1.9,-1.0) {wrong};
  % clean point
  \fill[black] (0,0) circle (2.4pt);
  \node[anchor=north, font=\footnotesize] at (0,-0.2) {clean};
  % gradient arrow (uphill on loss, toward boundary)
  \draw[->, acc, very thick] (0,0) -- (1.0,1.0)
    node[pos=0.6, anchor=south east, font=\footnotesize, text=acc] {\texttt{gradient}};
  % sign step lands at the corner (eps, eps)
  \draw[->, green, very thick, dashed] (0,0) -- (1.4,1.4);
  \fill[green] (1.4,1.4) circle (2.4pt);
  \node[green, font=\footnotesize, anchor=south west] at (1.4,1.4) {sign step};
\end{tikzpicture}
$$

## The linearity hypothesis

Why does a perturbation far too small for a human to notice swing the output so
violently? The early intuition blamed extreme nonlinearity. Goodfellow, Shlens and
Szegedy argued the opposite: deep networks are **too linear**, and the
damage is a high-dimensional dot-product effect.[^gf-linearity] Consider a single linear unit
$w^\top x$ and the worst-case $L_\infty$ perturbation $\delta = \epsilon\,
\sign(w)$:

$$
w^\top (x + \delta) \;=\; w^\top x \;+\; \epsilon\, w^\top \sign(w)
\;=\; w^\top x \;+\; \epsilon \sum_{j=1}^{d} |w_j|
\;=\; w^\top x \;+\; \epsilon\,\norm{w}_1.
$$

The activation shifts by $\epsilon\norm{w}_1$. The key is that this grows
with the dimension $d$ even though _each_ coordinate of $\delta$ is capped at
$\epsilon$. If the weights have average magnitude $\bar{|w|}$, then $\norm{w}_1 = d\,\bar{|w|}$, so the perturbation's effect on the activation is

$$
\epsilon\,\norm{w}_1 \;=\; \epsilon\, d\,\bar{|w|},
$$

**linear in $d$**, while the perturbation's per-pixel size stays fixed at
$\epsilon$. A model that operates on $d \sim 10^5$ pixels accumulates a hundred
thousand small aligned contributions into an activation shift large enough to
cross a class boundary, even though no individual pixel moved visibly.

$$
% caption: The dimension effect. With each coordinate capped at $\epsilon$, the activation shift $\epsilon\norm{w}_1$ still grows linearly in the dimension $d$.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  % axes
  \draw[->, thick] (0,0) -- (5.2,0) node[right, font=\footnotesize] {dimension $d$};
  \draw[->, thick] (0,0) -- (0,3.4) node[above, font=\footnotesize] {shift in \texttt{activation}};
  % linear growth line
  \draw[acc, very thick] (0,0) -- (4.6,3.0);
  \node[acc, font=\footnotesize, anchor=south east] at (4.5,1.5) {grows as $d$};
  % constant per-pixel cap reference
  \draw[black, dashed, thick] (0,0.55) -- (4.8,0.55)
    node[right, black, font=\footnotesize] {per-pixel cap eps};
  % sample dots on the line
  \foreach \x/\y in {1/0.65,2/1.30,3/1.96,4/2.61}
    \fill[acc] (\x,\y) circle (1.8pt);
\end{tikzpicture}
$$

> **Remark (Linearity hypothesis).** Modern networks are built from components
> (ReLU, maxout, linear layers) that are deliberately near-linear to keep gradients
> healthy for optimization. That same near-linearity makes them vulnerable: in high
> dimension a bounded $L_\infty$ perturbation aligned with the weights produces a
> change in the response that scales with $d$, so adversarial examples are a
> _consequence_ of the design choices that make deep nets easy to train, not an
> exotic pathology. They also **transfer**: because many models learn similar
> near-linear functions, an example crafted on one often fools another, enabling
> black-box attacks.

## PGD: the strong iterative attack

FGSM takes a single linearized step. But the loss is not actually linear, so one
big jump overshoots and underuses the budget. The fix is to iterate: take small
signed-gradient steps of size $\alpha$, and after each step **project** back onto
the $\epsilon$-ball so the cumulative perturbation never escapes the threat model.
This is **projected gradient descent** (PGD), the standard strong white-box attack.
For the $L_\infty$ ball the projection is a coordinate-wise clip:

$$
\Pi_{\mathcal{S}}(z)_j = \clip\parens{z_j,\; x_j - \epsilon,\; x_j + \epsilon},
$$

and the PGD iterate is

$$
x^{(t+1)} = \Pi_{\mathcal{S}}\!\parens{x^{(t)} + \alpha\,\sign\parens{\nabla_x \ell(x^{(t)}, y)}}.
$$

$$
% caption: PGD as a constrained path. Each step climbs the loss; a step leaving the $\epsilon$-box is projected back, so iterates crawl to the loss-maximizing corner.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % the L-infinity feasible box
  \draw[black, thick] (-2,-2) rectangle (2,2);
  \node[black, font=\footnotesize, anchor=north west] at (-1.95,-2.08) {feasible box};
  % start at the clean input
  \fill[black] (0,0) circle (2.4pt);
  \node[anchor=north, font=\footnotesize] at (0,-0.22) {start};
  % projected-gradient steps climbing toward the corner
  \draw[->, acc, very thick] (0,0) -- (1.0,0.9);
  \fill[acc] (1.0,0.9) circle (2.0pt);
  \draw[->, acc, very thick] (1.0,0.9) -- (1.95,1.75);
  \fill[acc] (1.95,1.75) circle (2.0pt);
  % the next step would leave the box (dashed) -> the excursion point
  \draw[->, acc, very thick, dashed] (1.95,1.75) -- (3.0,2.6);
  \draw[red, thick] (3.0,2.6) circle (2.4pt);
  \node[red, font=\footnotesize, anchor=west] at (3.14,2.6) {leaves box};
  % projection back onto the nearest in-box corner
  \draw[->, green, very thick] (3.0,2.6) -- (2,2);
  \fill[green] (2,2) circle (2.6pt);
  \node[green, font=\footnotesize, anchor=west] at (2.16,1.58) {\texttt{project back}};
\end{tikzpicture}
$$

Both attacks share the same skeleton (climb the loss in input space) and differ
only in the step count and the projection.

```algorithm
caption: $\textsc{Fgsm}(x, y, \epsilon)$ — one-step $L_\infty$ attack
$g \gets \nabla_x\, \text{loss}(x, y)$ // input-gradient at the clean point
$x' \gets x + \epsilon \cdot \text{sign}(g)$ // optimal linearized step
$x' \gets \text{clip}(x', 0, 1)$ // keep a valid image
return $x'$
```

```algorithm
caption: $\textsc{Pgd}(x, y, \epsilon, \alpha, T)$ — iterated, projected $L_\infty$ attack
$x' \gets x + \text{rand}(-\epsilon, \epsilon)$ // random start inside the box
for $t \gets 1$ to $T$ do
  $g \gets \nabla_x\, \text{loss}(x', y)$ // gradient at the current iterate
  $x' \gets x' + \alpha \cdot \text{sign}(g)$ // small ascent step
  $x' \gets x + \text{clip}(x' - x, -\epsilon, \epsilon)$ // project onto eps-box
  $x' \gets \text{clip}(x', 0, 1)$ // keep a valid image
return $x'$
```

The random start matters: it scatters the attack across the box and defeats
defenses that only flatten the loss at the single clean point, so multi-restart
PGD is the standard yardstick for measuring robustness.

The step size and count are coupled to the budget. A useful default keeps the
per-step move small relative to $\epsilon$ and takes enough steps to reach the wall:
with $T$ steps of size $\alpha$ the attack can travel up to $T\alpha$ in $L_\infty$,
so $T\alpha \gtrsim \epsilon$ is needed to cover the ball, and a common choice is
$\alpha = 2.5\,\epsilon / T$, which lets each coordinate reach either wall and then
bounce. Continuing the worked example with $\epsilon = 0.1$: choosing $T = 10$ gives
$\alpha = 0.025$, so a coordinate whose gradient sign stays fixed climbs
$0.025,\ 0.050,\ 0.075,\ 0.100$ over the first four steps, then the clip pins it at
$\pm 0.1$; later steps that would push past the wall are clamped back by the
projection $\Pi_\mathcal{S}$. Where the sign flips between steps the
iterate walks back off the wall — the non-linearity FGSM's single
step misses. PGD therefore finds a strictly higher inner-max loss than FGSM on
the same budget, and the gap is a direct measure of how non-linear the loss is
inside the ball.

## The canonical schematic

The textbook picture is one image: a clean input the model labels correctly (the
original panda at $58\%$), plus a small multiple of the signed gradient, equals an
adversarial input the model labels confidently wrong, a gibbon at $99\%$, yet the
two images are visually indistinguishable.

$$
% caption: The canonical construction. A correct input plus $\epsilon$ times the signed gradient gives a visually identical input that is confidently misclassified.
\begin{tikzpicture}[>=stealth, font=\small,
  img/.style={draw, minimum width=20mm, minimum height=20mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % clean
  \node[img, draw=green, thick] (clean) at (0,0) {clean\\input};
  \node[font=\footnotesize, text=green, anchor=north] at (0,-1.25) {true class, 58\%};
  % plus
  \node[font=\large] (plus) at (2.4,0) {$+$};
  % perturbation
  \node[img] (pert) at (4.8,0) {signed\\gradient};
  \node[font=\footnotesize, anchor=north] at (4.8,-1.25) {scaled by eps};
  % equals
  \node[font=\large] (eq) at (7.2,0) {$=$};
  % adversarial
  \node[img, draw=red, thick] (adv) at (9.6,0) {adversarial\\input};
  \node[font=\footnotesize, text=red, anchor=north] at (9.6,-1.25) {wrong class, 99\%};
\end{tikzpicture}
$$

## Robustness as a saddle point

If an attacker maximizes the loss over the perturbation set, the natural defense is
to train against that worst case. This turns ordinary empirical risk minimization
into a **min-max** (robust optimization) problem: minimize over parameters the
expected _worst-case_ loss the attacker can inflict.[^gf-advtrain]

> **Definition (Adversarial training).** Replace the standard objective
> $\min_\theta \mathbb{E}_{(x,y)}[\ell(x, y)]$ with the saddle-point problem
> $$
> \min_\theta \; \mathbb{E}_{(x,y)}\brackets{\max_{\norm{\delta}_p \le \epsilon}\;
> \ell(x + \delta, y)}.
> $$
> The inner $\max$ is solved approximately by an attack (FGSM or, better, PGD); the
> outer $\min$ is ordinary SGD on the resulting adversarial inputs. The network is
> trained on the hardest perturbed version of each example it can find.

The practical loop reuses the [training loop](/deep-learning/foundations/what-is-deep-learning)
with one inserted line: before each gradient step, replace the batch with its
adversarial counterpart from the inner attack.

```algorithm
caption: $\textsc{AdvTrain}(f_\theta, \mathcal{D}, \epsilon, \alpha, T)$ — min-max training
initialize $\theta$ randomly
repeat
  sample a minibatch $(X, y) \sim \mathcal{D}$
  $X' \gets \textsc{Pgd}(X, y, \epsilon, \alpha, T)$ // inner max: worst-case batch
  $L \gets \text{loss}(f_\theta(X'), y)$ // loss on the adversarial batch
  $\theta \gets \theta - \eta \cdot \nabla_\theta L$ // outer min: SGD step
until converged
return $\theta$
```

By the envelope theorem, differentiating through the inner maximum is valid: at the
optimal $\delta^\star$ the gradient with respect to $\theta$ is just $\nabla_\theta
\ell(x + \delta^\star, y)$ holding $\delta^\star$ fixed, which is why the loop above
can treat the attacked batch as ordinary data.

## The robustness–accuracy tradeoff

Robustness is not free. Fitting the worst case inside every $\epsilon$-ball forces
smoother, lower-capacity decision functions, and a model spending capacity to be
flat near the data has less left to chase the last points of clean accuracy. The
empirical and theoretical picture is a tradeoff: as the training budget $\epsilon$
rises, accuracy _under attack_ improves while accuracy on _clean_ data falls.

$$
% caption: The robustness–accuracy tradeoff. As the training budget $\epsilon$ grows, clean accuracy decays while robust accuracy rises then saturates.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, thick] (0,0) -- (5.6,0) node[right, font=\footnotesize] {training budget eps};
  \draw[->, thick] (0,0) -- (0,3.6) node[above, font=\footnotesize] {accuracy};
  \draw[black, dashed] (0,3.0) -- (5.2,3.0) node[black, right, font=\footnotesize] {100\%};
  % clean accuracy: starts high, decays
  \draw[green, very thick] plot[domain=0:5, samples=60] (\x, {3.0 - 0.09*\x*\x});
  \node[green, font=\footnotesize, anchor=west] at (5.15,0.75) {clean accuracy};
  % robust accuracy: starts at 0, rises and saturates
  \draw[red, very thick] plot[domain=0:5, samples=60] (\x, {2.0*(1 - exp(-0.9*\x))});
  \node[red, font=\footnotesize, anchor=west] at (5.15,1.98) {robust accuracy};
  % sweet-spot marker
  \draw[black, dashed] (2.0,0) -- (2.0,2.64);
  \node[black, font=\footnotesize, anchor=north] at (2.0,-0.05) {sweet spot};
\end{tikzpicture}
$$

> **Theorem (Tradeoff, informal).** There exist data distributions on which _no_
> classifier is simultaneously optimal for clean accuracy and for $L_\infty$-robust
> accuracy: the feature that maximizes standard accuracy is precisely the one an
> $\epsilon$-bounded adversary can flip, so robust and standard optima differ. The
> gap is not merely a limit of current methods; it is intrinsic to such
> distributions.

> **Proof (sketch).** Construct a distribution with one strongly-but-not-perfectly
> predictive "robust" feature and many weakly predictive "non-robust" features whose
> aggregate correlation with $y$ is high. A standard classifier leans on the
> non-robust features to squeeze out the last accuracy, since their combined signal
> is strong. An $\epsilon$-bounded $L_\infty$ adversary can flip the sign of each
> weak feature's contribution (exactly the dimension effect
> $\epsilon\norm{w}_1$), collapsing that aggregate. The only classifier the
> adversary cannot defeat ignores the non-robust features and pays in clean
> accuracy. Hence the two optima cannot coincide. $\qed$

Adversarial training buys robustness at a cost in clean accuracy. Whether a defense
can do better — whether robustness can be _proved_ rather than measured, and why so
many published defenses failed under stronger attacks — is taken up next.

This continues in [Adversarial Defenses](/deep-learning/theory/adversarial-defenses).

## Takeaways

- An **adversarial example** $x' = x + \delta$ with $\norm{\delta}_\infty \le
  \epsilon$ is an imperceptible perturbation that flips the prediction; every claim
  of robustness is relative to a **threat model** (norm ball, white-box vs.
  black-box, targeted vs. untargeted).
- **FGSM**, $x' = x + \epsilon\,\sign(\nabla_x\ell)$, is the exact
  maximizer of the linearized loss over the $L_\infty$ ball: steepest ascent in the
  $L_\infty$ norm, just as ordinary gradient ascent is steepest in $L_2$.
- The **linearity hypothesis** explains the severity: a bounded $L_\infty$
  perturbation shifts a linear unit's activation by $\epsilon\norm{w}_1 =
  \epsilon\,d\,\bar{|w|}$, **linear in the dimension** $d$ — many small aligned
  per-pixel moves sum to a large shift, and such examples **transfer** across models.
- **PGD** iterates FGSM with a projection back into the $\epsilon$-ball; multi-restart
  PGD is the standard strong white-box benchmark, and it finds a strictly higher
  inner-max loss than FGSM's single jump.
- **Adversarial training** is the min-max problem $\min_\theta \mathbb{E}[\max_\delta
  \ell(x+\delta, y)]$: SGD on PGD-attacked batches. It buys robustness at a real cost
  in clean accuracy, an intrinsic **tradeoff** on some distributions — the handoff to
  [the defense side](/deep-learning/theory/adversarial-defenses).

[^gf-adv]: **Goodfellow**, _Deep Learning_, §7.13 — Adversarial Training: imperceptible $L_\infty$-bounded perturbations that flip a correct prediction.
[^gf-fgsm]: **Goodfellow**, _Deep Learning_, §7.13 — the fast gradient sign method $x + \epsilon\,\mathrm{sign}(\nabla_x\ell)$ as the linearized-loss maximizer over the $L_\infty$ ball (Goodfellow, Shlens & Szegedy, 2015).
[^gf-linearity]: **Goodfellow**, _Deep Learning_, §7.13 — the linearity hypothesis: high-dimensional near-linear models accumulate aligned perturbations into a shift of $\epsilon\norm{w}_1$, growing with dimension.
[^gf-advtrain]: **Goodfellow**, _Deep Learning_, §7.13 — adversarial training as the min-max objective $\min_\theta\mathbb{E}[\max_\delta \ell(x+\delta,y)]$, i.e. SGD on attacked batches.