On the Convergence and Robustness of Adversarial Training

In plain words

Adversarial training teaches a network to resist attacks by training it on inputs that an attacker has nudged to fool it. The attacker's search for those nudges is never perfect, and the paper asks how good a search has to be. It proposes a score that tells you how close an attack is to the best nudge it could find for a given input. Watching that score shows that the early part of training works better with weaker, easier attacks, and that the later part needs stronger ones. The proposed method starts with weak attacks and makes them stronger over time, and it trains a more robust model than standard adversarial training does.

TL;DR

Adversarial training with PGD is among the most effective defenses against adversarial examples, but how well the inner attack is solved has not been measured. The paper defines FOSC, a first-order stationarity score for the inner maximisation, and uses it to monitor and control attack strength. A dynamic schedule that lowers the FOSC threshold linearly over training gives higher author-reported robustness on MNIST and CIFAR-10 than standard PGD training. Use it if you train robust classifiers and want a stopping rule for the inner attack.

Problem

Adversarial training solves a min-max problem: the inner maximisation finds a perturbed input within an ε-ball that maximises the loss, and the outer minimisation fits the parameters on those inputs eq. 1 §1. The paper argues that the quality of the inner solve drives the robustness of the outer step §1, but that no criterion existed to measure that quality for attacks such as FGSM eq. 2 or PGD eq. 3 §1 §2.1. Without such a criterion, training is hard to monitor and improve §1. The analysis assumes a constrained, locally strongly concave inner problem and smoothness of the loss; the paper states that Danskin's theorem does not strictly hold for ReLU networks, and it argues for an approximate-maximiser guarantee instead §4.2.

Method

FOSC criterion §3.1. For an input x^k inside the ε-ball X around x^0, with loss f(θ, x) and label y, the criterion is the maximum over X of the inner product of (x − x^k) with the input gradient at x^k eq. 4. It is nonnegative, and smaller values mean a better inner solution. The paper gives a closed form that uses only the L1 norm of the gradient and the displacement from x^0 §3.1. A criterion of value δ means x^k is a δ-approximate maximiser eq. 5 §4.2.

Observations §3.2. On CIFAR-10 with PGD-10 (step ε/4, ε = 8/255), FOSC correlates roughly linearly with test accuracy and loss of the adversarial examples fig. 1. Each PGD step lowers FOSC towards zero, while loss rises and flattens fig. 1. The best final robustness among step sizes and step counts tracks lower FOSC distributions, not lower loss distributions fig. 2. Early in training, FOSC is much lower than later, which the paper reads as overfitting to strong PGD examples early on. Replacing the first 20 epochs of PGD with one-step FGSM gives higher final robustness and a more concentrated FOSC distribution later fig. 3 §3.2.

Dynamic adversarial training §4.1, alg. 1. Training uses PGD examples whose FOSC must fall below a threshold c_t that decreases over epochs. The threshold is c_t = max(c_max − t · c_max / T′, 0) §4.1. At each PGD step, examples whose FOSC is already at or below c_t stop moving alg. 1. The paper suggests estimating c_max from the mean FOSC of FGSM examples §4.1, but its experiments use a fixed value §5.1. T′ is slightly below the total epoch count T, so the last epochs run at threshold zero §4.1.

# Dynamic adversarial training  [alg. 1] [§4.1]
# Input:  model with parameters theta, data S, c_max, total epochs T,
#         threshold epochs T_prime, outer step size eta_t
# Output: trained parameters theta

def dynamic_adversarial_training(model, data, c_max, T, T_prime):
    # Loop over epochs t = 0 .. T-1  [alg. 1]
    for t in range(T):
        # Threshold falls linearly from c_max to 0 at T_prime  [§4.1]
        c_t = max(c_max - t * c_max / T_prime, 0.0)
        for batch_x0, batch_y in data:
            # Generate FOSC-controlled adversarial examples  [alg. 1]
            batch_adv = pgd_with_fosc_stop(model, batch_x0, batch_y, c_t)
            # Outer step on the adversarial batch  [alg. 1] [eq. 1]
            theta = theta - eta_t * loss_gradient(model, batch_adv, batch_y)
    return theta

# PGD with per-example stop on FOSC  [alg. 1] [§4.1]
# Input:  batch_x0 (B, d), batch_y (B,), threshold c_t
# Output: batch_x (B, d), within epsilon of batch_x0 in L-inf norm

def pgd_with_fosc_stop(model, batch_x0, batch_y, c_t):
    # Start from the normal input; the experiments use a random start [§5.1]
    batch_x = batch_x0
    # Control vector V: 1 means the example is still being attacked  [alg. 1]
    active = ones_like(batch_y)
    for step in range(K):  # K steps; step size alpha  [alg. 1] [§5.1]
        grad = loss_gradient_wrt_input(model, batch_x, batch_y)
        # Ascent step, applied only to active examples  [alg. 1] [eq. 3]
        batch_x = batch_x + active * alpha * sign(grad)
        # Project onto the epsilon-ball around batch_x0  [alg. 1] [eq. 3]
        batch_x = clip(batch_x, batch_x0 - epsilon, batch_x0 + epsilon)
        # Keep attacking only while FOSC is above the threshold  [alg. 1]
        fosc = fosc_value(grad, batch_x, batch_x0, epsilon)
        active = fosc > c_t
        # Stop early when no example is active  [alg. 1]
        if not any(active):
            break
    return batch_x

# FOSC value, closed form  [§3.1]
# Input:  grad (B, d) loss gradient w.r.t. the input at x
# Output: fosc (B,)

def fosc_value(grad, x, x0, epsilon):
    # Epsilon times the L1 norm of the input gradient  [§3.1]
    grad_l1 = sum(abs(grad), over input dimensions)      # (B,)
    # Inner product of the displacement from x0 with the gradient  [§3.1]
    displacement = x - x0                                # (B, d)
    inner = sum(displacement * grad, over input dimensions)  # (B,)
    return epsilon * grad_l1 - inner

Convergence analysis §4.2, thm. 1, app. A. Assumptions: gradient Lipschitz conditions [Assumption 1]; local μ-strong concavity in the ε-ball [Assumption 2]; bounded gradient variance σ² [Assumption 3]. With outer step η = sqrt(Δ / (T · L · σ²)) and T ≥ ΔL / σ², where Δ = L_S(θ⁰) − min L_S and L = L_θx · L_xθ / μ + L_θθ, the average squared gradient norm of the min-max objective is bounded by 4σ·sqrt(LΔ/T) + 2 · L_θx² · δ / μ [thm. 1]. The bound holds when FOSC ≤ δ on every example. The discussion takes this to mean that the outer loop approaches a stationary point, with a remaining error that grows with δ §4.2.

Relation to curriculum learning §4.3. The paper treats FOSC as a difficulty measure, so dynamic training is a curriculum. It contrasts this with the curriculum of Cai et al., which uses PGD step count as the difficulty, and argues that more steps can overshoot §4.3.

Hyperparameters

Results

Author-reported. Setup: white-box and black-box attacks on the test set, ε as in the hyperparameter table, MNIST and CIFAR-10 with the small CNNs §5.1. Table 3 uses the WideResNet setting §5.2. The black-box surrogate for CIFAR-10 is a ResNet-50 §5.1.

White-box accuracy (%) tab. 1

Black-box accuracy (%) tab. 2

WideResNet, CIFAR-10 white-box accuracy (%), Madry's setting tab. 3

Headline: on CIFAR-10 with the 8-layer CNN, Dynamic reaches 48.06% under PGD-10 against 44.39% for Standard tab. 1. On MNIST, Dynamic has the highest PGD-10, PGD-20 and C&W∞ values in tab. 1; Curriculum is higher on FGSM and on clean accuracy tab. 1 §5.1.

Paper vs code

Code: YisenWang/dynamic_adv_training at commit 470210e23941a2faca804e83e0f17cf58d913707, owner is the first author. The repository has no LICENSE file, so do not copy code verbatim. The code is cited by path and line only. The repository has a training script, a PGD attack, a loss, a logger and a model file. It has no script that produces the tables in the paper.

• Training attack and FOSC: the PGD loop, the closed-form FOSC and the control mask match the paper's description pgd_attack.py §3.1 alg. 1. The code runs all nb_iter steps on the batch and freezes finished examples with a mask, instead of stopping the loop early pgd_attack.py pgd_attack.py alg. 1. The effect on the examples is the same, but the batch still pays for every step.
• Threshold schedule: the linear schedule uses fosc_max and dynamic_epoch and matches §4.1 train_models.py. Defaults are 0.5 and 100 for CIFAR-10 train_models.py.
• Learning rate: the code drops the rate at epochs 60 and 100 of 120 for CIFAR-10, as the paper states train_models.py §5.1. No MNIST schedule is in the script.
• Weight decay: the paper states weight decay 1e-4 §5.1. The code passes decay=1e-4 to Keras SGD train_models.py. In Keras this argument is a learning-rate decay per update, not an L2 penalty. The code applies no weight decay term. Confirm against the Keras version used.
• Per-example loss weights: from the second epoch on (ep > 0), the code multiplies each example's loss by its cross-entropy on the adversarial input train_models.py train_models.py. The paper does not describe this weighting.
• Architecture for CIFAR-10: the paper's main table uses an 8-layer CNN. The code builds a WideResNet of depth 5 for CIFAR-10 models.py. The CIFAR-10 CNN is in a commented-out block models.py, which uses 64, 128 and 196 filters with a 256-unit dense layer. The MNIST model matches the paper's description models.py.
• Epsilon: the paper states 8/255 §5.1. The run passes 0.031 train_models.py. 8/255 is about 0.0314.
• Data augmentation: the paper states none §5.1. The code applies rotation, shifts and horizontal flips to CIFAR-10 train_models.py.
• Attack evaluation: the repository has a TestLinfPGDAttack class with a C&W-style loss pgd_attack.py. It has no script that runs the FGSM, PGD-10, PGD-20 and C&W∞ evaluations of tab. 1 to tab. 3, and no black-box surrogate training. The "Curriculum" baseline and the Madry WideResNet baseline are not in the code.
• Batch size: not stated in the paper, default 128 in the code train_models.py.
• Clean-input range: the data loader scales inputs to [0, 1] when clip_max is 1 datasets.py.

Pitfalls

• Printed indicator in alg. 1 is inverted. The line that sets the control vector writes an indicator that is 1 where FOSC is at most c_t, but its own comment says the element becomes 0 where FOSC is smaller than c_t alg. 1. The code freezes examples at or below the threshold and keeps attacking the rest pgd_attack.py. The card's pseudocode follows the code and the comment. Using the printed formula would attack the wrong examples.
• Tie at the threshold. The code uses <= for freezing [code: pgd_attack.py#L91]. The paper says "smaller than" alg. 1. This matters only for exact ties, which are rare in float32.
• Threshold reaches zero. From epoch T′ on, c_t is zero. Examples then stop only when FOSC is exactly zero, so these epochs are close to standard 10-step PGD with a random start §4.1 alg. 1. For CIFAR-10 this is epochs 100 to 119 of 120. This is an inference from the update rule and the stopping rule, not a stated result.
• Cost of FOSC. The FOSC of the current point reuses the gradient already computed for the next PGD step pgd_attack.py. There is no extra gradient pass for the criterion. The freezing mask saves no compute in the code, because all steps still run on the full batch pgd_attack.py.
• Per-example loss weights change the objective. The weighted loss train_models.py is not in the paper, so an implementation from this card will not reproduce the code's numbers without it.
• Constants never measured. The paper's theorem uses L, μ, σ² and δ. The experiments do not estimate them §4.2. The bound therefore does not predict the reported numbers. The paper says the strong-concavity assumption is checked through the link to distributionally robust optimisation §4.2. It does not show that the assumption holds for these networks.
• c_max is fixed, not estimated. The paper suggests estimating c_max from FGSM examples §4.1 but uses 0.5 for every run §5.1. The code also uses a constant train_models.py. No estimation code exists.
• Cross-entropy clipping. The training loss renormalises the softmax output and clips probabilities to [ε, 1 − ε] for the float epsilon of Keras losses.py. The attack gradient uses the logits through a softmax with an added 1e-20 pgd_attack.py. The attack's sign-based steps depend only on the gradient's sign, so the two choices can differ on very confident examples. The code does not show which one the paper's numbers used.
• Version dependence. The README pins Python 3.5.2, TensorFlow 1.10.1 and Keras 2.2.2 [README]. The code uses the TensorFlow 1 placeholder and gradient API pgd_attack.py. Porting it needs an explicit choice of how the Keras learning-rate decay maps to the paper's weight decay.
• Arxiv version. This card follows arXiv v2, dated 2022-04-23. It is the ICML 2019 accepted version with a proof appendix §4.2 app. A.

Lineage

• Builds on: standard PGD adversarial training of Madry et al., cited as madry2017towards §2.2 §5.1. The paper changes the inner attack's stopping rule and the training schedule.
• Compared against: curriculum adversarial training of Cai et al., cited as cai2018curriculum, which grows the PGD step count §5.1 §4.3. The dynamic schedule uses FOSC rather than step count as the difficulty.
• Related criterion: the Frank-Wolfe gap, cited as frank1956algorithm, which the FOSC criterion is inspired by §3.1.