Adversarial Training and Certified Defences
The min-max formulation behind the only empirical defence that has held up, what a certificate actually guarantees, and the gap between certified and empirical robustness.
Dozens of defences have been proposed and most were broken within a year of publication. Two approaches have survived: adversarial training, which is empirical and expensive, and certification, which is provable and weak. Understanding why the first works and the second is limited explains most of the field's shape.
Adversarial training
The formulation (Madry et al., 2018, arXiv:1706.06083) is a saddle point problem:
The inner maximisation finds the worst perturbation within the allowed set; the outer minimisation trains against it. Solving the inner problem approximately with projected gradient descent, several steps of gradient ascent on the loss with projection back into the ball after each, and training on the resulting examples, is the whole method.
It works, in the sense that it produces genuine robustness that adaptive attacks do not trivially defeat. It costs a factor equal to the number of PGD steps in training time, since each training example requires an inner optimisation, so 7-step PGD training is roughly seven times more expensive than standard training. And it reduces clean accuracy, typically by a meaningful margin on ImageNet-scale problems.
The robustness it produces is specific to the threat model it trained against. A model adversarially trained on \(\ell_\infty\) at \(\epsilon = 8/255\) is substantially more vulnerable to \(\ell_2\) attacks and to larger \(\epsilon\), which is a direct consequence of the inner maximisation being over a fixed set.
Certification
A certified defence provides a proof: for this input, no perturbation within radius \(r\) changes the prediction. That is a categorically stronger claim than surviving known attacks, because it covers attacks not yet invented.
Randomised smoothing is the approach that scales. Define a smoothed classifier that returns the most likely class when the input is perturbed with Gaussian noise, estimate that by sampling, and derive a certified \(\ell_2\) radius from the margin between the top two class probabilities (Cohen et al., 2019, arXiv:1902.02918). The guarantee is probabilistic, holding with high confidence over the sampling, and it requires many forward passes per prediction, often hundreds or thousands, which puts it out of reach for latency-sensitive deployment.
Deterministic methods based on interval bound propagation or convex relaxation give exact certificates for small networks and become loose, giving vacuous radii, as networks grow.
When it breaks
Certified radii are small. Certified accuracy at radii that matter practically is far below empirical robust accuracy at the same radius. The certificate is a lower bound and the gap is large, so certification tells you what is provable rather than what is true.
Adversarial training on a proxy threat model can mislead. A production system's real adversary is not norm-bounded, so robustness measured against PGD may not correspond to robustness against the attack that actually arrives. The measurement is meaningful; the extrapolation is not.
Evaluation must be adaptive. A defence has to be attacked by someone who knows how it works and designs against it. Standardised ensembles such as AutoAttack exist because fixed-attack evaluation systematically overstates robustness, and a robustness number without an adaptive evaluation is not evidence.
Robustness and fairness interact. Adversarial training's accuracy cost is not uniform across classes or subgroups; it tends to fall harder on classes that were already harder. A robustness intervention can therefore worsen disparity, which is not visible in aggregate robust accuracy.
12 flashcards for this concept
Click a card to reveal the answer.