Exercises — Adversarial examples and robustness

"At most, per pixel" is the definition of the ==$L_{\infty }$ norm==: $\Vert \mathbf{\delta }{\Vert }_{\infty }={\max }_i|{\delta }_i|$. The bound is $ϵ=\frac{4}{255}\approx 0.0157$. Why not $L_2$? $L_2$ would bound the total length across all pixels, letting one pixel change hugely if others stay still. Here the cap is on each pixel individually, which is exactly what $L_{\infty }$ measures.

FGSM sets ${\delta }_i=ϵ\cdot \mathrm{sign}\left(\frac{\partial \mathcal{L}}{\partial x_i}\right)$. Since the gradient is negative, $\mathrm{sign}(-3.7)=-1$, so ${\delta }_i=\frac{8}{255}\cdot (-1)=-\frac{8}{255}\approx -\mathrm{0.03137.}$ Notice: the magnitude $3.7$ is thrown away. Under $L_{\infty }$, all that matters is the direction (sign) — every coordinate gets pushed the full $ϵ$, never more, never less.

Step 1 — signs: $\mathrm{sign}([+2.0,-0.5,+4.0])=[+1,-1,+1]$. Step 2 — perturbation: $\mathbf{\delta }=0.1\cdot [+1,-1,+1]=[+0.1,-0.1,+0.1]$. Step 3 — add: ${\mathbf{x}}_{\text{adv}}=[0.50,0.20,0.90]+[0.1,-0.1,0.1]=[0.60,0.10,1.00]$. Check the budget: $\Vert \mathbf{\delta }{\Vert }_{\infty }=0.1=ϵ$. ✓

Targeted FGSM subtracts: ${\mathbf{x}}_{\text{adv}}=\mathbf{x}-ϵ\cdot \mathrm{sign}({\nabla }_{\mathbf{x}}\mathcal{L}(\theta ,\mathbf{x},t))$. Signs: $\mathrm{sign}([-1.0,+3.0,0.0])=[-1,+1,0]$. Note the exact zero: $\mathrm{sign}(0)=0$. Perturbation: $-0.1\cdot [-1,+1,0]=[+0.1,-0.1,0.0]$. ${\mathbf{x}}_{\text{adv}}=[0.50,0.20,0.90]+[0.1,-0.1,0.0]=[0.60,0.10,0.90]$. Why subtract? For untargeted we climb the loss of the true label. For targeted we want the model to prefer class $t$, i.e. lower the loss of $t$ — descending, hence the minus sign.

Step 1 (gradient): ${\mathbf{x}}^{(1)}=[0.50,0.50]+0.04\cdot [+1,+1]=[0.54,0.54]$. Project to the $ϵ$-ball around ${\mathbf{x}}^{(0)}$: clip each coord to $[0.50-0.10,0.50+0.10]=[0.40,0.60]$. Both $0.54$ are inside → ${\mathbf{x}}^{(1)}=[0.54,0.54]$ (blue point in the figure). Step 2 (gradient): $[0.54,0.54]+0.04\cdot [+1,-1]=[0.58,0.50]$. Project: both inside $[0.40,0.60]$ → ${\mathbf{x}}^{(2)}=[0.58,0.50]$ (green point). Budget check: $\Vert {\mathbf{x}}^{(2)}-{\mathbf{x}}^{(0)}{\Vert }_{\infty }=\max (0.08,0.00)=0.08\le 0.10$. ✓ — the green point sits comfortably inside the yellow box.

Write the dot product coordinate-by-coordinate: ${\mathbf{\delta }}^{\top }\mathbf{g}={\sum }_i{\delta }_i{g}_i$. The constraint $\Vert \mathbf{\delta }{\Vert }_{\infty }\le ϵ$ means each ${\delta }_i$ independently satisfies $|{\delta }_i|\le ϵ$ — the coordinates don't trade off against each other (unlike $L_2$). So we maximise each term ${\delta }_i{g}_i$ separately. For a fixed $g_i$, the product ${\delta }_i{g}_i$ over ${\delta }_i\in [-ϵ,ϵ]$ is largest when ${\delta }_i$ has the same sign as $g_i$ and is as big as allowed: ${\delta }_i=ϵ\mathrm{sign}(g_i)$. Then ${\delta }_i{g}_i=ϵ|g_i|$. Summing: $\max ={\sum }_iϵ|g_i|=ϵ{\sum }_i|g_i|=ϵ\Vert \mathbf{g}{\Vert }_1.$ So the best-case first-order loss increase is $ϵ\Vert \mathbf{g}{\Vert }_1$ — the $L_1$ norm of the gradient shows up because it is the "dual" of the $L_{\infty }$ ball.

FGSM ($L_{\infty }$): increase $=ϵ\Vert \mathbf{g}{\Vert }_1=0.1\cdot (2.0+0.5+4.0)=0.1\cdot 6.5=0.65$. Best $L_2$ step of length $0.1$: the optimal direction points along $\mathbf{g}$ itself, giving increase $=ϵ\Vert \mathbf{g}{\Vert }_2$. Here $\Vert \mathbf{g}{\Vert }_2=\sqrt{4+0.25+16}=\sqrt{20.25}=4.5$, so increase $=0.1\cdot 4.5=0.45$. Reading it: $L_{\infty }$ (FGSM) achieves a larger first-order increase ($0.65>0.45$) for the same per-coordinate budget, because it independently maxes out every coordinate. But note the $L_{\infty }$ step has a longer Euclidean length ($\Vert \mathbf{\delta }{\Vert }_2=0.1\sqrt{3}\approx 0.173$), so it isn't a free lunch — it just uses a bigger box.

Why $L_2$ here, not $L_{\infty }$? The point of this exercise is to hold the perceptibility measure — Euclidean length — constant and watch how effectiveness scales with dimension. FGSM's $L_{\infty }$ step would instead fix the per-coordinate size and let the Euclidean length grow, which mixes two effects. To isolate "does dimension alone help the attacker?", we bound $\Vert \mathbf{\delta }{\Vert }_2=ϵ$. Optimal $L_2$ direction. Under a fixed Euclidean length, ${\mathbf{\delta }}^{\top }\mathbf{g}$ is maximised by pointing $\mathbf{\delta }$ along $\mathbf{g}$ (Cauchy–Schwarz): $\mathbf{\delta }=ϵ\mathbf{g}/\Vert \mathbf{g}{\Vert }_2$. With all $|g_i|=c$ and equal sign, this puts an equal share into every coordinate: ${\delta }_i=\pm ϵ/\sqrt{d}$. That is why we "spread $ϵ$ evenly" — it is not an arbitrary choice, it is the forced consequence of the gradient being uniform. Check the length: $\Vert \mathbf{\delta }{\Vert }_2=\sqrt{d\cdot (ϵ/\sqrt{d}{)}^2}=ϵ$. ✓ Loss increase. ${\mathbf{\delta }}^{\top }\mathbf{g}={\sum }_i\frac{ϵ}{\sqrt{d}}c=d\cdot \frac{ϵc}{\sqrt{d}}=ϵc\sqrt{d}.$ So with a fixed, imperceptible Euclidean nudge, the loss increase scales as $\sqrt{d}$. For a $224\times 224\times 3$ image, $\sqrt{d}=\sqrt{150528}\approx 388$ — a factor-of-hundreds amplification, purely from dimension count. This is the geometric root of vulnerability: many tiny aligned nudges sum to a large effect. High dimensions help the attacker, not the defender.

For each batch (X, y):
    X_adv = X.detach()  + random_start in [-eps, eps]   # inner max via PGD
    repeat T times:
        g = grad_x  L(theta, X_adv, y)                  # attack step
        X_adv = X_adv + alpha * sign(g)
        X_adv = clip(X_adv, X - eps, X + eps)           # project to L_inf ball
        X_adv = clip(X_adv, 0, 1)                        # valid pixel range
    X_adv = X_adv.detach()                               # freeze the attack result
    loss = CrossEntropy(model(X_adv), y)                 # outer min
    loss.backward(); optimizer.step()                    # update theta

(a) Detach the attack: The inner $\max$ is solved approximately by PGD and treated as a fixed data-augmentation. If we differentiated through the whole PGD chain, gradients would explode in cost and instability; Madry et al. use Danskin's theorem, which says that to first order it suffices to evaluate the outer gradient at the worst-case ${\mathbf{\delta }}^{\star }$ and treat that ${\mathbf{\delta }}^{\star }$ as constant. Hence stop-gradient. (b) Still backprop the model: The outer ${\min }_{\theta }$ is what actually learns robustness — it updates $\theta$ so that even the worst-case perturbed input is classified correctly. Without this backward pass on $\theta$, no learning happens at all.

Let one training-pass mean exactly one forward pass through the network plus one backward pass — the two operations every gradient computation needs. (Standard training does exactly one such pass per batch.) Standard training: 1 forward + 1 backward per batch = $1$ training-pass. PGD-$T$ attack: each of the $T$ steps needs a forward pass and a backward pass to the input to get ${\nabla }_{\mathbf{x}}\mathcal{L}$ → $T$ training-passes. Then the outer update needs 1 more forward + 1 backward on $\theta$ → 1 training-pass. Total $\approx (T+1)$ training-passes. Multiplier over standard $=\frac{T+1}{1}=T+1$. For $T=7$: $7+1=8\times$ the compute. (This is the well-known reason robust training is expensive.)

With $\alpha =ϵ$ and $T=1$ and no random start, "PGD" collapses into a single FGSM step — the weakest attack in the family. A model can then exploit gradient masking (a.k.a. obfuscated gradients): it arranges its loss surface so that the local input gradient near clean images is uninformative — for example by saturating activations so ${\nabla }_{\mathbf{x}}\mathcal{L}\approx 0$ or points in a useless direction — so a single-step attack finds nothing to climb. Yet the true decision boundary is still close: a stronger attacker (many small steps with $\alpha \ll ϵ$, multiple random restarts, or a transfer/black-box attack that never uses the defender's own gradient) still crosses it easily. The phenomenon: gradient masking / obfuscated gradients. The reported "100%" measures resistance to a crippled one-step attacker, not genuine robustness. Fix / diagnosis: evaluate with strong PGD ($\alpha \approx ϵ/4$, $T\ge 20$, several random restarts) and cross-check with a gradient-free or transfer attack. Telltale signs of masking: accuracy that stays pinned at 100% then collapses abruptly as $ϵ$ grows (instead of degrading smoothly), or single-step attacks beating iterative ones. See Out-of-distribution detection for the complementary problem of inputs far from the data manifold.

Lipschitz means any input change of size $\Vert \mathbf{\delta }{\Vert }_{\infty }$ moves any logit by at most $L\Vert \mathbf{\delta }{\Vert }_{\infty }$. The gap between the top logit and a runner-up can shrink at most twice as fast (top can fall by $Lϵ$, runner-up can rise by $Lϵ$), so the gap stays positive as long as $m-2Lϵ>0⟹ϵ<\frac{m}{2L}.$ Certified radius ${ϵ}_{\text{cert}}=\frac{m}{2L}=\frac{0.6}{2\cdot 2.5}=\frac{0.6}{5}=0.12.$ Reading it: larger margin $m$ → more room; smaller Lipschitz constant $L$ → flatter, more predictable model → bigger certified radius. This is why robustness research pushes for large margins and Lipschitz control, and it links back to Interpretability and explainability: a certifiably smooth model is also easier to reason about. For the broader safety picture see AI Safety fundamentals and note the contrast with Reward hacking, where the failure is in the objective, not the input.

Could you… state which norm a bound describes? ::: Ex 1.1 Compute an FGSM and a targeted-FGSM step by hand? ::: Ex 2.1, 2.2 Run PGD with projection and verify the budget? ::: Ex 2.3 Prove $ϵ\mathrm{sign}(\mathbf{g})$ is optimal and get $ϵ\Vert \mathbf{g}{\Vert }_1$? ::: Ex 3.1 Explain the $\sqrt{d}$ dimensional amplification under a fixed $L_2$ length? ::: Ex 3.3 Write the Madry inner/outer loop and justify stop-gradient? ::: Ex 4.1 Give the $T+1$ compute multiplier? ::: Ex 4.2 Diagnose gradient masking from a suspicious "100%"? ::: Ex 5.1 Derive a certified radius $m/(2L)$? ::: Ex 5.2