Module 6 · 6 min read
Certified Robustness, Empirical Robustness and the Trade-off
What a certificate actually bounds, why certified numbers sit below measured ones, and how to choose a perturbation budget as a risk decision.
Certified robustness and empirical robustness answer different questions and carry different weights, and confusing them is one of the most consequential errors in this field, because it usually happens in front of people making funding and deployment decisions. An empirical result says: we attacked it and this is how we did. A certificate says: for these points, we can prove that nothing inside this specific region changes the prediction. The proof is worth a great deal, and the region is much smaller than most readers assume.
A vision model ships with a certificate of 62 percent certified accuracy at an L2 radius of 0.5. An executive reads this as 62 percent of attacks against the model failing. The correct reading is different in kind. For 62 percent of the evaluation points, it is provable that no perturbation with L2 norm at most 0.5 changes the prediction. Everything outside that statement is uncovered: perturbations of L2 norm 0.6, perturbations measured in any other norm, and semantic transformations such as rotation, translation, cropping, lighting change, compression, or in the language setting, paraphrase and synonym substitution. It is also not an empirical average over an attack suite, and it will not be pushed downward by a stronger attack published next year, because it is a proof rather than a measurement. One qualifier travels with that and you must carry it: certificates come in two kinds. Verification-based ones, complete verification and bound propagation, are deterministic. Randomised smoothing, which is what an L2 certificate on a realistic vision model almost always rests on, gives a high-probability statement at a stated confidence level, obtained by sampling, and about a smoothed classifier rather than the base model. Both are proofs in the sense that matters here, in that no future attack revises them, but they are not the same object. Ask which kind you are being shown before you quote the number.
Certified versus empirical
Select a card to turn it over.
Check yourself
For the same model at the same radius, a team reports 62 percent certified accuracy and 71 percent measured accuracy against the strongest attack they could mount. A reviewer says one of the numbers must be wrong. Who is right?
Verification methods are sound but incomplete: they fail to certify many points that are in fact robust, so certified accuracy normally sits below measured robust accuracy and the gap narrows as verification improves. The two numbers also differ in how much they can be trusted: the certified figure cannot be reduced by a cleverer attack, whereas the measured figure can.
Be candid about the state of the art when someone asks whether to buy certified robustness. Certified radii that are meaningful against realistic threat models remain small on complex tasks, and the accuracy cost of the training regimes that make certification possible is substantial. Certification for language models is largely an open problem: the results that exist are typically confined to narrow, enumerable perturbation sets such as a fixed synonym substitution list, which is a long way from certifying against paraphrase. Presenting certification as a general solution to adversarial robustness misrepresents it. Presenting it as a rigorous, narrow guarantee that is genuinely unbreakable within its stated bounds is accurate, and in some regulated settings that narrow guarantee is exactly what is wanted.
The robustness and accuracy trade-off
Adversarial training at a large epsilon raises robust accuracy and costs several points of clean accuracy on the production distribution. A director asks for both to be maximised. The principled response starts by refusing the premise: for current methods the trade-off is real and consistently observed. Whether it is fundamental or an artefact of present techniques and dataset sizes is genuinely debated, and the honest position is that it depends on the data distribution and is not settled. What is settled is that you cannot presently have both, so someone must choose.
That makes epsilon a risk decision rather than a compute decision. Derive it from the perturbations your threat model actually contains, and from the relative cost of the two error types: a false accept on a fraud screen and a false reject on a fraud screen do not cost the same, and neither do a missed defect and a spurious alarm on an inspection line. Then report both clean and robust accuracy on the deployment distribution, not on a benchmark, because the benchmark is not the population you will serve. Three tempting answers are wrong: that the trade-off is a defect in the training loop, that it disappears with more data, and that clean and robust accuracy are independent quantities.
Try it first
Why is setting epsilon as large as the compute budget allows the wrong instinct?
Two reasons, worth separating. First, on the mathematics: a certificate at a large radius does contain the smaller radii inside it, but adversarial training at a large epsilon does not monotonically improve robustness at the small epsilon you actually face, and it reliably costs clean accuracy on every ordinary prediction the system makes. Second, and more important commercially: epsilon should be derived from the threat model and the cost of each error type, not from available hardware. Buying robustness at a radius nobody will ever attack, and charging for it on every normal input, is a poor trade dressed up as diligence.