Adversarial Robustness

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 $\Vert \delta {\Vert }_{\infty }\le ϵ$ for some tiny $ϵ$ (a few gray levels out of $255$), and the model's prediction flips with high confidence. The perturbed input $x^{\prime }=x+\delta$ is an adversarial example.¹ 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 that linear readouts draw near the data.

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 :\Vert \delta {\Vert }_p\le ϵ\}$, and the two norms that dominate the literature carve out very different shapes.

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:

To maximize the loss we maximize the inner product $g^{\top }\delta$, writing $g={\nabla }_x\ell (x,y)$, subject to $\Vert \delta {\Vert }_{\infty }\le ϵ$. This is a tiny constrained optimization with a closed form: each coordinate ${\delta }_j$ is free in $[-ϵ,ϵ]$ 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.

That optimal ${\delta }^{\star }$ is the fast gradient sign method (FGSM).² The maximum achievable first-order loss increase is $ϵ\Vert g{\Vert }_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 \Vert g{\Vert }_q\Vert \delta {\Vert }_p$ with $1/p+1/q=1$. For $p=\infty$ the dual is $q=1$, giving the bound $ϵ\Vert g{\Vert }_1$, attained by $\delta =ϵ\mathrm{sign}(g)$. Change the constraint and the optimal step changes with it: under an $L_2$ budget $\Vert \delta {\Vert }_2\le ϵ$ the dual is $q=2$, the bound is $ϵ\Vert g{\Vert }_2$, and the maximizer is the normalized gradient ${\delta }^{\star }=ϵg/\Vert g{\Vert }_2$ — ordinary steepest ascent. Each norm ball selects the steepest-ascent direction in its own geometry: FGSM is steepest ascent measured in $L_{\infty }$.

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 $ϵ=0.1$, FGSM sets each coordinate to $x_j+ϵ\mathrm{sign}(g_j)$:

Every pixel moved by exactly $ϵ$ 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=ϵ\Vert g{\Vert }_1$, matching the bound. Had we instead used the raw gradient step $x+ϵg=(0.58,0.48,0.54)$, the largest coordinate would have moved only $0.08<ϵ$: it underuses the $L_{\infty }$ budget on the small-gradient pixels. The sign is what saturates every coordinate to the box wall.

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.³ Consider a single linear unit $w^{\top }x$ and the worst-case $L_{\infty }$ perturbation $\delta =ϵ\mathrm{sign}(w)$:

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

linear in $d$, while the perturbation's per-pixel size stays fixed at $ϵ$. 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.

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 $ϵ$-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:

and the PGD iterate is

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

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 $ϵ$ 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 ϵ$ is needed to cover the ball, and a common choice is $\alpha =2.5ϵ/T$, which lets each coordinate reach either wall and then bounce. Continuing the worked example with $ϵ=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.

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.⁴

The practical loop reuses the training loop with one inserted line: before each gradient step, replace the batch with its adversarial counterpart from the inner attack.

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 $ϵ$-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 $ϵ$ rises, accuracy under attack improves while accuracy on clean data falls.

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.

Takeaways

• An adversarial example $x^{\prime }=x+\delta$ with $\Vert \delta {\Vert }_{\infty }\le ϵ$ 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^{\prime }=x+ϵ\mathrm{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 $ϵ\Vert w{\Vert }_1=ϵd\overline{|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 $ϵ$-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.