Learning the Cheap Attack: Fast Adversarial Training as a Stochastic Bilevel Problem

Adversarial training makes a classifier robust by training it on worst-case perturbed inputs. Its cost comes from the attack, not the model: finding those perturbations with a multi-step attack multiplies training time by roughly ten. The cheap alternative takes one gradient-sign step from a smart starting point. It recovers most of the robustness, but it can fail without warning through catastrophic overfitting: the model learns a jagged loss surface that defeats the single step, and its robustness against real attacks falls to near zero. Today's fixes choose the starting point by hand-designed rules. Some store each training example's perturbation from earlier epochs, some blend old and new perturbations using a confidence score, and some use a small generator trained to maximize loss on the current model. None of them trains the starting point for what the practitioner actually wants, which is a model that ends up robust.

We propose to train a small initialization generator directly for that goal. The upper-level objective is the multi-step-attack loss of the model a few steps later on a held-out batch. The lower level is the ordinary fast adversarial training of the classifier. This is a stochastic bilevel problem: an outer optimization whose objective depends on the result of an inner one, with only noisy mini-batches available at both levels. We solve it with the first-order, single-loop, multi-timescale machinery that the bilevel optimization literature has developed but rarely tested at deep-learning scale. The generator is updated slowly, the classifier quickly, and hypergradients are estimated by finite differences of ordinary gradients, never by second derivatives or by backpropagating through training. The idea from the transferability literature is the meta-train/meta-test split: perturbations are crafted on one model and scored on a different one. Here the "different model" is the defender's own future checkpoint.

Core Claim

The current methods that prevent catastrophic overfitting all implicitly rely on temporal transferability: a perturbation built for an earlier version of the model is still adversarial for the current one. The epoch buffers of Prior-Guided Adversarial Initialization for Fast Adversarial Training rely on it, and so does the confidence-weighted fusion in Preventing Catastrophic Overfitting in Fast Adversarial Training: A Bi-level Optimization Perspective. Enhancing Adversarial Transferability with Checkpoints of a Single Model's Training gives independent evidence that checkpoints of one training run differ enough to act as diverse surrogate models for attacks. We claim that this temporal transfer can be optimized rather than assumed.

Concretely, let $g_\phi$ be a generator with parameters $\phi$ that maps an image $x$ and its gradient sign to an initial perturbation $\eta$. Let $\delta_\phi(x,\theta)$ be the perturbation obtained by one projected gradient-sign step from $\eta$ on the classifier with parameters $\theta$. The method solves

$$\min_\phi \; \mathcal{L}_{\text{val}}^{\text{PGD}}\big(\theta^*(\phi)\big) \quad \text{s.t.} \quad \theta^*(\phi) \in \arg\min_\theta \; \mathbb{E}_{(x,y)}\, \ell\big(f_\theta(x+\delta_\phi(x,\theta)),\, y\big),$$

where $\mathcal{L}_{\text{val}}^{\text{PGD}}$ is the cross-entropy of the classifier under a multi-step attack on a small held-out batch, and $\ell$ is the training loss.

The new piece is the hypergradient: the derivative of robust validation loss with respect to the generator, estimated online at a cost of a few extra gradient evaluations every $k$ steps. It replaces three things in current methods: per-sample memory buffers, confidence heuristics, and the "maximize loss on the current model" signal used by Boosting Fast Adversarial Training With Learnable Adversarial Initialization. We do not expect large gains in headline CIFAR-10 accuracy, because the strongest existing method already beats multi-step training there. We expect three narrower results. First, accuracy matching the best buffer-based methods without per-sample storage, which makes ImageNet-scale training feasible. Second, no catastrophic overfitting across a wide grid of learning rates and step sizes. Third, measurably better robustness against attacks transferred from other architectures, because the generator is trained on a cross-checkpoint transfer signal.

Relation to Prior Work

Three fast-training methods supply the setting and the competitors.

Fast is better than free: Revisiting adversarial training showed that a random start before the single gradient-sign step prevents catastrophic overfitting. The method stays sensitive to step sizes and schedules, and we use it as the naive reference.

The prior-guided initialization paper (FGSM-MEP) and the bi-level-perspective paper (FGSM-PCO) seed the single step with historical perturbations. Both use bilevel language only as intuition: neither estimates a hypergradient. They are constrained by per-sample buffers, which the file notes become a memory burden at ImageNet scale. PCO is also constrained by a confidence heuristic that may degrade with thousands of overlapping classes.

FGSM-SDI is the closest in mechanism, since it also trains a three-layer generator. Its generator is trained to find local worst-case directions on the current network, alternating with the classifier and with no convergence argument. We keep its architecture and its update-every-$k$ schedule and change only what the generator is trained for. That makes the decisive ablation clean.

The transferability literature supplies the meta-train/meta-test idea.

Meta Gradient Adversarial Attack crafts perturbations on some surrogate models and updates them by their success on a held-out one. It costs about 67 seconds per image against 19 seconds for its base attack, which is why we refuse to backpropagate through attacks.

Meta Adversarial Perturbations meta-learns a single starting perturbation from which one step is potent. On CIFAR-10 ResNet-18 that one step drops accuracy to 20.3% versus 41.4% for plain FGSM, which is direct evidence that learned starting points make one step much stronger. It relies on second-order meta-gradients, which we avoid.

Advancing Generalized Transfer Attack with Initialization Derived Bilevel Optimization and Dynamic Sequence Truncation is the closest formulation. It optimizes an attack's starting point so the resulting perturbation hurts a held-out pseudo-victim, and it truncates backpropagation through the attack to save compute. It is purely offensive, uses fixed models, and computes hypergradients by unrolling. We differ in three ways: our pseudo-victim is the defender's own moving future checkpoint, the upper objective is the defender's robustness, and our hypergradient is first-order and single-loop. Training Meta-Surrogate Model for Transferable Adversarial Attack shows the memory cost of backpropagating through smoothed multi-step attacks, a design we rule out for the same reason.

The optimization literature supplies the solver.

A Two-Timescale Stochastic Algorithm Framework for Bilevel Optimization shows that updating the inner variable fast and the outer variable slowly filters mini-batch noise without running the inner problem to convergence. It proves rates only for strongly convex inner problems, which a deep classifier is not.

Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization approximates the needed second-derivative products by finite differences of gradients, and maintains an auxiliary vector with a single-loop update. Its optimal rate is proven only in the deterministic setting, and the file lists the noisy mini-batch extension as open. Our setting is a demanding, practically motivated test of exactly that extension. The Jensen-type bias of stochastic hypergradients is a measurable quantity here, not just a theoretical worry.

Adversarially Robust Few-Shot Learning: A Meta-Learning Approach is a reminder that meta-learned robustness methods tend to inherit full multi-step attack costs. We hold ourselves to a compute budget close to single-step training.

Research Program

The classifier $\theta$ trains with standard single-step adversarial training on perturbations from $g_\phi$. It takes every mini-batch step, which makes it the fast timescale.

Every $k$ steps, an auxiliary vector $v$ is updated on a medium timescale. It tracks the damped inverse Hessian of the training loss applied to the validation-loss gradient. The update uses one finite-difference Hessian-vector product: two training-loss gradients at $\theta \pm r v$.

The generator then takes a slow step along the estimated hypergradient. That hypergradient is the negative mixed derivative applied to $v$, again obtained by finite differences: the generator gradient of the training loss evaluated at $\theta + rv$ minus at $\theta - rv$, divided by $2r$. Computing a generator gradient only requires backpropagating through the generator, because the sign step is treated as having identity derivative with respect to $\eta$ inside the projection.

The validation loss uses a multi-step attack on a small held-out batch, and it is evaluated after the classifier has taken $m$ further steps. This lookahead is what makes the signal temporal transfer, not current-model worst case. Per $k$ steps, the overhead is one small multi-step attack plus about four gradient evaluations.

The analysis has three parts. First, we measure hypergradient bias and variance directly. Small-batch estimates are compared against large-batch, long-inner-loop reference estimates at frozen checkpoints, across finite-difference radii $r$, damping values, and timescale ratios. Second, we track a temporal-transfer statistic throughout training: the loss on model $\theta_{t+m}$ of perturbations built at $\theta_t$. We test whether drops in it precede catastrophic overfitting, analogous to the attack-success-rate warning signal reported for FGSM-MEP. Third, under a lower-level Polyak-Łojasiewicz assumption (a condition guaranteeing that gradient descent makes steady progress), we aim to state a stochastic convergence result for the finite-difference estimator. If such a result cannot be obtained, we will treat the empirical bias measurements as the evidence instead.

Baselines

The naive reference is FGSM with random initialization from Fast is better than free, which reports 45% robust accuracy against strong PGD on CIFAR-10 in six minutes. Its close relative FGSM-RS is reported at 42.31% PGD-10 in the FGSM-SDI paper. It defines the floor and the cost unit: every method's wall-clock is reported as a multiple of it.

Standard multi-step adversarial training is the quality reference. FGSM-PCO reports 53.19% PGD-10 for it, and FGSM-MEP reports 53.76%, both on CIFAR-10 ResNet-18.

The strongest existing competitor is FGSM-PCO, at 56.32% PGD-10 on CIFAR-10 ResNet-18, with 0 of 10 runs collapsing on CIFAR-100 WideResNet34-10 where FGSM-MEP collapsed in 6 of 10. It is the strongest because it already exceeds multi-step training and is the only method with a published stress-test record. FGSM-MEP (55.18%) is the second buffer-based competitor. FGSM-SDI (53.73% on CIFAR-10; 66.8 versus 211.2 hours against multi-step training on ImageNet) is the strongest buffer-free competitor. We found no reported ImageNet result on Lacuna for FGSM-PCO or FGSM-MEP, and no reported result on Lacuna for any fast method's robustness against transferred black-box attacks.

All baselines run from their released or described configurations, on our hardware, with the same architectures, epochs, perturbation budget, and data augmentation. Each method gets an equal tuning budget over its own hyperparameters, chosen on the same held-out split. Beating PCO on CIFAR-10 means a statistically significant gain in PGD-50 accuracy over five seeds; matching it within one point while using no per-sample buffer also counts as success. On the stress test, success means no more collapses than PCO across a wider learning-rate and step-size grid. On ImageNet, success means beating SDI's robust accuracy at no more than 1.3 times its wall-clock.

Two ablations isolate the key ingredient, each with an identical generator and compute.

The first trains $g_\phi$ to maximize loss on the current model, which is SDI's objective. It separates "learned initialization" from "bilevel transfer objective."

The second keeps the robust-validation objective but sets the lookahead $m=0$, which isolates the temporal-transfer component.

A third variant computes the hypergradient by unrolling one classifier step with truncated backpropagation, in the style of the BETAK paper's sequence truncation. It isolates whether the two-timescale finite-difference solver matters at all.

Why not just…?

Why not just use FGSM-PCO, which already beats multi-step training? On CIFAR-scale benchmarks it may well tie us, and we say so. Its weaknesses are structural. It stores a perturbation per training example, and the file flags such epoch buffers as a memory burden at ImageNet scale. It also fuses perturbations with a confidence heuristic, which is likely fragile with many classes. The ImageNet and CIFAR-100 comparisons test both weaknesses directly. If PCO matches us on ImageNet and on the wider hyperparameter grid, the proposal's practical claim fails.

Why not just update the FGSM-SDI generator more often or make it larger? That changes how much SDI optimizes, not what it optimizes for. It still chases the current model's local worst case, which is the very signal that a jagged, overfit loss surface corrupts. The first ablation, run with the same generator at a matched update frequency, settles this.

Why not just backpropagate through one unrolled training step instead of building a stochastic bilevel solver? This is the most serious threat. A one-step unrolled hypergradient costs about the same and may be good enough. The third ablation compares them on robust accuracy, collapse rate, and measured hypergradient bias. If unrolling ties, we will report that the two-timescale finite-difference machinery is unnecessary in this regime, and the contribution reduces to the objective.

Why not just detect catastrophic overfitting with a PGD validation check and roll back, as Fast is better than free does with early stopping? Detection loses the epochs after collapse and does not prevent the collapse. Our method uses the same validation signal as a training gradient instead of a stop rule. The stress-test collapse counts and final accuracies show which is better.

Proposed Experiments

On CIFAR-10 and CIFAR-100 we use ResNet-18 and WideResNet34-10 with an $\ell_\infty$ budget of 8/255. We also run a larger budget, where single-step training is more fragile; no reported fast-training numbers at that budget were found in the file. Metrics are PGD-10 and PGD-50 robust accuracy, clean accuracy, wall-clock, and peak memory.

The stress test repeats the 10-seed CIFAR-100 WideResNet34-10 protocol from the FGSM-PCO paper and extends it across a grid of learning rates and step sizes. The outcome is the fraction of runs that collapse.

On ImageNet with ResNet-50 we compare against FGSM-SDI and multi-step training on robust accuracy and hours, and we report the buffer memory that FGSM-MEP and PCO would require.

To test transfer robustness, each defended model is attacked with black-box perturbations crafted on held-out architectures using MGAA-style and checkpoint-ensemble attacks. The prediction is that the lookahead objective improves this metric over SDI and PCO even where white-box accuracy ties.

The decisive checks are two. First, the full method must beat the current-model-objective ablation on collapse rate and transfer robustness at equal compute; if it does not, the bilevel objective adds nothing. Second, the finite-difference hypergradient must show lower bias than the truncated-unroll estimate at equal cost; if it does not, the stochastic bilevel solver is unnecessary.