Projected Gradient Descent (PGD)

Unlike single-step attacks, PGD applies the Fast Gradient Sign Method (FGSM) repeatedly with a small step size α. After each step, the perturbation is projected back onto the Lp-norm ball (typically L∞) to ensure the adversarial example stays within the allowed threat model.

• Process: x_{t+1} = Π_{x+S} (x_t + α * sign(∇_x J(θ, x_t, y)))
• Key Insight: This iterative process finds a much stronger local maximum of the loss function than single-step methods.
• Standard Setting: Often uses 40 steps (PGD-40) with a step size of ε/10.

The 'Projected' in PGD refers to the mathematical projection Π that constrains the perturbation. After each gradient step, if the perturbation δ exceeds the allowed budget ε, it is projected back onto the surface of the Lp-ball.

• L∞ Norm: The most common constraint, limiting the maximum change to any single pixel to ε.
• L2 Norm: Constrains the Euclidean distance of the perturbation.
• L1 Norm: Used for sparse perturbations.
• Purpose: Ensures the attack remains imperceptible or within a defined physical limit.

A critical component of a strong PGD evaluation is random initialization. Instead of starting from the original input, the attack begins at a random point within the allowed ε-ball.

• Avoiding Local Minima: This prevents the optimizer from getting stuck in a shallow local maximum of the loss landscape near the starting point.
• Standard Practice: Multiple random restarts are performed, and the worst-case example is selected.
• Gradient Masking Detection: If a defense fails against PGD with restarts but survives without them, it is a strong indicator of obfuscated gradients.

PGD is considered a universal first-order adversary, meaning it is the strongest possible attack using only first-order (gradient) information. If a model is robust against PGD, it is empirically robust against all gradient-based attacks.

• Benchmark Standard: PGD is the primary attack used in RobustBench to rank defenses.
• Adaptive Evaluation: Defenses must be tested against PGD with full knowledge of the defense mechanism (white-box) to be considered valid.
• Relationship to Training: Adversarial training uses PGD to generate the training data, making it the de facto standard for building robust models.

The core objective of PGD is to solve the constrained optimization problem: maximize the model's loss subject to the perturbation being within the allowed set S.

• Formulation: max_{δ∈S} L(θ, x+δ, y) where S = {δ : ||δ||_p ≤ ε}.
• Cross-Entropy: Typically maximizes the cross-entropy loss to push the model away from the correct class.
• Targeted Variant: Can be adapted to minimize loss towards a specific target class, creating a targeted attack.

While FGSM is a single, large step to the boundary of the ε-ball, PGD refines this over many small steps. This makes PGD a significantly stronger attack.

• FGSM: x_adv = x + ε * sign(∇_x J(θ, x, y)) (one step).
• PGD: Iterates FGSM with a smaller step size α < ε and projects.
• Result: Defenses that block FGSM often fail catastrophically against PGD, a phenomenon known as gradient masking.
• Computational Cost: PGD is k times more expensive than FGSM, where k is the number of iterations.

The foundational single-step precursor to PGD. FGSM generates an adversarial example by taking a single large step in the direction of the loss gradient sign: x' = x + ε · sign(∇xJ(θ, x, y)). While computationally cheap, it severely underestimates model vulnerability compared to multi-step methods. PGD is essentially an iterative application of FGSM with a random start and projection step.

The primary defensive technique against PGD attacks. It augments the training dataset with adversarial examples generated on-the-fly. The standard approach uses PGD to craft the strongest possible perturbations during training, solving a min-max optimization problem:

• Inner Maximization: PGD finds the worst-case perturbation.
• Outer Minimization: The model learns to classify these perturbed inputs correctly. This remains the most empirically robust defense against Lp-bounded attacks.

The mathematical constraint defining the adversary's power. PGD projects perturbations onto an Lp-norm ball of radius ε, ensuring the perturbation magnitude is bounded:

• L∞ (Infinity Norm): Limits the maximum change to any single pixel. The most common setting for image classifiers.
• L2 (Euclidean Norm): Limits the total magnitude of the perturbation vector.
• L1 (Manhattan Norm): Limits the sum of absolute changes, often promoting sparse perturbations.

A brittle defense that PGD is specifically designed to expose. Gradient masking occurs when a defense obfuscates the model's gradients rather than removing the underlying vulnerability. This creates a false sense of security because single-step attacks like FGSM fail, but multi-step PGD attacks with random restarts can still find adversarial examples by circumventing the non-differentiable or saturated components of the defense.