Adversarial Training - Inner Maximization

How The Inner Maximization Is Solved

The inner $\max$ is itself an optimization problem and is approximated by gradient ascent on the input.

FGSM (Fast Gradient Sign Method) takes a single step in the sign of the input gradient:

$$\delta =ϵ\cdot \text{sign}\left({\nabla }_x\mathcal{L}(f_{\theta }(x),y)\right)$$

FGSM is fast (one extra forward-backward) but weak — a one-step linear approximation often misses the worst-case perturbation. Example: for a handwritten 7, FGSM produces a perturbed image that still looks like a 7 to humans but the model misclassifies as 1.

PGD (Projected Gradient Descent) iterates FGSM and projects back onto the $ϵ$-ball after each step:

$${\delta }_{t+1}={\Pi }_{\Vert \delta {\Vert }_p\le ϵ}\left({\delta }_t+\alpha \cdot \text{sign}\left({\nabla }_x\mathcal{L}(f_{\theta }(x+{\delta }_t),y)\right)\right)$$

PGD with random restart is the standard “strong” attack used to evaluate robustness. Training on PGD-generated examples (Madry-style adversarial training) is the most common reliable defense, at the cost of roughly $K\times$ more compute per step where $K$ is the number of inner iterations.