FGSM fired once is a single guess. Fired again and again — each step's overshoot projected back into an ε-box around the input — it becomes the strongest first-order attack we know. PGD climbs the loss surface inside the box and is forbidden to leave it: x ← clipε( x + α·sign ∇Loss ). Down the center the input goes in, the iterates ascend, the adversarial example comes out. The blue team builds the projection and proves it holds; the red team rips the projection out and the perturbation escapes.
source Madry, Makelov, Schmidt, Tsipras, Vladu, Towards Deep Learning Models Resistant to Adversarial Attacks (2017) — arxiv.org/abs/1706.06083. Rendered, not quoted.
So every adversarial quantity has an exact answer, the target is a fixed logistic classifier — weights known, not learned:
w = [1.5, −2.0, 0.5, 1.0], b = 0.5, input x₀ = [0.4, 0.2, −0.3, 0.1], true label +1. Logit z = w·x+b, loss = log(1+e−z).
Because the model is linear, ∇xLoss = −(1−σ(z))·w — its sign is constant (= −sign w), whatever z is. So the ascent direction never turns, and PGD marches straight to one vertex of the box.
The projection is the exact clip Πε(v)=min(max(v, x₀−ε), x₀+ε), applied per coordinate. Current perturbation δ = xfinal − x₀:
| coord | δᵢ | |δᵢ| ≤ ε ? |
|---|
PGD is the FGSM iterated. One FGSM step is x₀+ε·sign ∇Loss — a single leap to the box corner. PGD takes many small α-steps and re-projects, so on a curved loss it can find a higher point than one leap.
But on this linear model the sign never changes, so PGD lands on the same vertex FGSM reaches in one shot — the engine asserts they agree to 1e-9. PGD is the inner max of adversarial training's min–max: the attack that defines empirical robustness. Each sphere is the next one's premise.
The blue team's live check: re-run PGD over the current settings and confirm every iterate stayed inside the ε-ball and the trajectory ended on the FGSM vertex. If red tears out the projection, this badge is where it shows.
Feed the engine three things: the clean input x₀, a perturbation budget ε (the L∞ radius — every coordinate may move at most ε), and a step size α. The adversary's goal: maximize the loss of the true label without leaving the box.
The feasible set is the ℓ∞ ball {x : ‖x−x₀‖∞ ≤ ε} — a hypercube of side 2ε centred on x₀. Nothing the attack produces is allowed outside it. That constraint is the whole discipline, and it is what you feed the panel below.
L∞ / PGD: climb the loss inside the ε-box; each overshoot clipped back to the wall.
| k | z | loss | ‖δ‖∞ | in box |
|---|
Change ε, α or steps — the trajectory, the loss climb and the vertex are computed on the spot from w, b and the projection, never looked up.
What the machine produces, proven: for the linear target, PGD's trajectory never leaves the ε-ball (‖xk−x₀‖∞ ≤ ε at every step), the loss is non-decreasing across steps, and PGD ends on the exact FGSM vertex x₀−ε·sign(w) — all checked to 1e-9. At ε=0.1 the logit falls z: 0.65 → 0.15 (drop = ε‖w‖₁ = 0.5), and the closed-form minimal-L₂ flip needs distance 0.2373 = |z₀|/‖w‖₂.
The blue team's witness (left) re-checks the ε-bound live; the red team (right) tries to make the perturbation escape it.
On a real (nonconvex) network the loss surface has many local maxima; a single run can undershoot, so honest PGD needs random restarts and careful α. And ℓ∞ is only one threat model — an ℓ∞-robust model can still fall to ℓ2, rotations, or unrestricted attacks.
"PGD certifies a model is robust." Cut. It is an empirical lower bound on adversarial risk — it finds attacks, it cannot prove their absence. Certification is a separate tool.
"More PGD steps always means a stronger attack." Cut. Returns diminish once the vertex is reached; past that, restarts and step size matter, not step count — here 5 steps already saturate.
"FGSM and PGD are fundamentally different attacks." Kept, corrected. On a linear model they hit the identical vertex (the engine proves it); PGD's edge appears only where the loss curves.
The red team's move: skip the projection step. Without the clip, x + α·sign∇Loss just keeps walking — the perturbation is no longer budget-bounded and the iterates leave the ε-box. The blue team's witness (window 7) is watching.
Skip the clip and after a few α-steps ‖δ‖∞ exceeds ε — the witness recomputes, sees an iterate outside the box, and turns red. Nothing is faked; the escape is real and it is caught.