Adversarial training hardens a neural network by training it on inputs that have been deliberately perturbed to fool it. It is expensive because each training step must first search for a bad perturbation. The cheap version uses a single gradient step for that search. It works until, without warning, it stops working: the model learns to defeat one-step attacks while remaining defenseless against stronger multi-step ones, a collapse called catastrophic overfitting. Separately, game-theoretic work has shown that standard adversarial training sets the attacker's goal wrongly. The attacker maximizes cross-entropy loss, a smooth stand-in for "being wrong," and can raise that loss simply by making the model less confident on points it still classifies correctly. The proposed fix makes the attacker maximize the classification margin instead, that is, push the most likely wrong class above the true class, while the defender keeps minimizing cross-entropy. This fix currently costs a targeted attack against every wrong class, which is far too slow for large label spaces.
This note proposes putting the two together. A single-step attacker plays a best response: it proposes cheap one-step targeted perturbations toward only the few most threatening wrong classes and keeps whichever one comes closest to flipping the label. The hypothesis is that much of catastrophic overfitting comes from the misaligned attacker. Single-step cross-entropy ascent gives the defender perturbations that lower confidence without crossing the decision boundary, and the defender learns to bend its loss surface locally against exactly those. An attacker aligned with misclassification should give stable fast training, cut the cost of the margin-based (non-zero-sum) game from one attack per class to a handful, and spend the perturbation budget only where a label can actually flip. That last property should cost less clean accuracy.
Core Claim
Adversarial Training Should Be Cast as a Non-Zero-Sum Game (BETA-AT) recasts adversarial training as a game in which the attacker and the defender have different objectives. The attacker maximizes the negative margin, the logit of a wrong class minus the logit of the true class, and the defender minimizes cross-entropy on the resulting points. The paper reports that this removes robust overfitting, the slow decline in test robustness late in training. It runs multi-step targeted attacks against all incorrect classes, though, and the paper acknowledges this is prohibitive at ImageNet scale.
Fast is better than free: Revisiting adversarial training shows that one-step training started from a random point inside the perturbation ball (FGSM-RS) can reach 45% robust accuracy on CIFAR-10 in 6 minutes, against 80 hours for standard multi-step training. It is fragile to the step size, and the authors leave unexplained why it works and why it collapses. Gap 3 of the file points out that no game-theoretic account of that collapse exists.
The claim is concrete. Consider a single-step, top-$k$ best-response version of the margin game, built as follows. For input $x$ with label $y$ and logits $z(\cdot)$, let $C_k(x)$ be the $k$ incorrect classes with the highest logits. For each $j \in C_k(x)$, the attacker forms one targeted step from a random start $\eta$:
$$\delta_j = \Pi_\epsilon\big(\eta + \alpha\, \mathrm{sign}\, \nabla_x [z_j - z_y](x+\eta)\big), \qquad \delta^\star = \arg\max_{j \in C_k(x)} \big[z_j - z_y\big](x+\delta_j).$$
Here $\Pi_\epsilon$ projects back into the $\ell_\infty$ ball of radius $\epsilon$, and $\alpha$ is the step size. The defender then takes one cross-entropy step on $x+\delta^\star$. The claim is that this procedure, at roughly $(k+1)$ forward-backward passes with $k \le 4$, has three properties. It avoids catastrophic overfitting across step sizes and budgets where FGSM-RS collapses. Under AutoAttack it comes within a small gap of multi-step training. And at matched robustness it loses less clean accuracy than cross-entropy-based fast training.
Research Program
The work has three parts. The first is building and characterizing the method. All $k$ targeted gradients share one forward pass and are computed by replicating the batch $k$ times for the backward pass, so the cost scales as roughly $(k+1)$ passes against 2 for FGSM-RS. The same harness runs every variant: cross-entropy single-step, margin single-step with $k=1$, top-$k$ best response, and multi-step BETA over all classes. Only the attacker's objective and candidate set change.
The second part is a mechanistic diagnostic meant to test the hypothesis, not just the method. At every epoch, we log the fraction of training perturbations that lower true-class confidence without changing the predicted label. We call these "wasted" perturbations. We also log the cosine alignment between the one-step input gradient and the direction of a 10-step attack, a standard sign of the local loss surface going nonlinear. The prediction is that under FGSM-RS the wasted fraction rises and gradient alignment falls in the epochs just before catastrophic overfitting, and that neither happens under the best-response attacker. If gradient alignment collapses under both attackers anyway, the misalignment explanation is wrong. That outcome is worth reporting.
The third part is the accuracy trade-off. Robust error splits into natural error plus the error of points sitting near the decision boundary (Theoretically Principled Trade-off between Robustness and Accuracy). A misclassification-seeking attacker should mostly move points that are close to the boundary and leave points deep inside a class roughly where they are. We test this by plotting clean accuracy against AutoAttack robust accuracy across a sweep of $\epsilon$ and training length, and by measuring, for each training example, how far it is from the boundary when it gets perturbed.
Baselines
The naive reference point is standard training with no adversarial component. It gives the clean-accuracy ceiling, near-zero robustness, and the baseline wall-clock time. Every cost figure is reported as a multiple of it.
The strongest fast competitor is FGSM-RS from Fast is better than free, using its cyclic learning rate and mixed precision. The reported reference is 45% robust accuracy on CIFAR-10 against PGD in 6 minutes, and 43% on ImageNet-1k in 12 hours. With it we run the two catastrophic-overfitting remedies in the file, Rethinking Fast Adversarial Training: A Splitting Technique to Overcome Catastrophic Overfitting and Preventing Catastrophic Overfitting in Fast Adversarial Training: A Bi-level Optimization Perspective. These directly target the failure mode our hypothesis is about. The file contains no reported numbers for either, so we reproduce both.
The strongest expensive references are multi-step PGD training, TRADES, and full BETA-AT. TRADES reports 56.61% white-box robust accuracy on CIFAR-10. The file has no reported robust-accuracy number for BETA-AT; it reports only that the BETA attack matches AutoAttack while running 5.11 times faster. We also include the margin-maximizing cross-entropy loss of Building Robust Ensembles via Margin Boosting. Its single ResNet-18 rises from 50.95% to 51.86% robust accuracy at about 5% overhead, which makes it a cheap way to add margin awareness on the defender's side rather than the attacker's.
The ablation that isolates the key ingredient keeps the step count fixed and varies only the attacker. The arms are cross-entropy ascent, a single margin step against the top runner-up ($k=1$), and the top-$k$ best response ($k=2,4$).
For fairness, every method uses the same architectures: PreAct ResNet-18 and WideResNet on CIFAR, ResNet-50 on ImageNet. Every method also gets the same data, the same augmentation, and an equal hyperparameter search budget over step size and learning rate, with five seeds each. Results are reported at matched epochs and at matched wall-clock time. To beat FGSM-RS and the two remedies, the method must have zero collapsed seeds over a step-size sweep in which they collapse in a meaningful fraction of runs, and equal or higher AutoAttack accuracy at no more than about twice their cost. To beat the expensive references, it must land within about two points of PGD and BETA-AT under AutoAttack while using a fraction of their compute. On CIFAR-100, it must match full BETA-AT at that lower cost.
Why not just…?
Why not just use FGSM with a margin loss instead of cross-entropy? This is our $k=1$ arm, and it is the real threat. If it matches top-$k$ on stability, robustness, and clean accuracy, the contribution shrinks to "use an aligned objective in fast training." That finding is still useful because it would explain catastrophic overfitting, but the best-response mechanism would be unnecessary. We expect $k>1$ to matter most when the runner-up class at the clean input is not the one that is easiest to reach within the perturbation ball, which should be more common on CIFAR-100 and ImageNet than on CIFAR-10. The ablation, reported separately per dataset, settles this. If $k=1$ wins everywhere, the note will say so.
Why not just use an existing catastrophic-overfitting fix such as the splitting technique or the bi-level reformulation? These remedies treat the symptom: they change the training dynamics while keeping the cross-entropy attacker. If they stabilize training just as well at equal cost, our method must still show an advantage on clean accuracy or on scaling to many classes. If it shows neither, the alignment story does not buy anything practical. We run both under the identical step-size sweep, so the comparison is head to head and not against numbers taken from the papers.
Why not just run TRADES or PGD training and tune the trade-off weight? That works when compute is free. The 80-hour figure against 6 minutes reported in Fast is better than free is why it is not the answer. TRADES also keeps a cross-entropy-style surrogate attacker, which BETA-AT argues is misaligned. The trade-off plots will show whether TRADES at a well-chosen weight dominates our method's frontier. If it does at equal compute, our method loses.
Why not just mix a standard and a robust model after training? Mixing classifiers to alleviate the accuracy-robustness trade-off reaches clean accuracy approaching 95% with 30–40% PGD accuracy on CIFAR-10. It still needs a robust model, which someone has to train, and it doubles inference cost. Our method can supply that robust component more cheaply, so the two are complementary. We report the mixture built on top of our model as a secondary result.
Proposed Experiments
The main experiments run on CIFAR-10 and CIFAR-100 at $\ell_\infty$ budgets $\epsilon = 8/255$ and $16/255$. The larger budget is included because one-step training is most fragile there. Step size is swept from $0.75\epsilon$ to $2\epsilon$ with five seeds per setting. All robust accuracy is measured with AutoAttack (Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks) under the RobustBench protocol. That paper found inflated robustness claims in 48 of 49 audited models, so PGD-only numbers will not be used to support any claim. The ImageNet-1k experiment compares top-$k$ best response to FGSM-RS at the 12-hour scale and to full BETA-AT on a 100-class subset, where full BETA-AT is still affordable. This tests the claim that cost drops from one attack per class to $k$ attacks.
Three outcomes decide the proposal. The first is the collapse count: how many seeds and settings end with near-zero AutoAttack accuracy under each attacker. The second is whether the diagnostic logged during training predicts collapse under FGSM-RS and stays flat under the best-response attacker. The third is the clean-versus-robust frontier at matched wall-clock time. If collapse persists under the aligned attacker, or the diagnostic does not separate the two attackers, the central hypothesis is false. If the method is stable but the $k=1$ margin step does equally well everywhere, the proposal reduces to its simplest ablation, and that is how it will be reported.
References
- Adversarial Training Should Be Cast as a Non-Zero-Sum Game
- Fast is better than free: Revisiting adversarial training
- Theoretically Principled Trade-off between Robustness and Accuracy
- Rethinking Fast Adversarial Training: A Splitting Technique to Overcome Catastrophic Overfitting
- Preventing Catastrophic Overfitting in Fast Adversarial Training: A Bi-level Optimization Perspective
- Building Robust Ensembles via Margin Boosting
- Mixing classifiers to alleviate the accuracy-robustness trade-off
- Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks
- RobustBench: a standardized adversarial robustness benchmark