An attack that fails proves nothing; a certificate proves a no-attack zone. If a classifier's Lipschitz constant is bounded by L, then around an input x with top-two-logit margin m the ball of radius m / (√2·L) is guaranteed flip-free — no perturbation inside it can change the predicted class. Down the center, data flows: the point and its margin go in, the certifier computes the radius, the proven safe ball comes out. The blue team builds and defends the proof; the red team tries to break it.
source Y. Tsuzuku, I. Sato, M. Sugiyama, Lipschitz-Margin Training (NeurIPS 2018) — arxiv.org/abs/1802.04034; margin/Lipschitz certification back to Szegedy et al. 2013 (arxiv.org/abs/1312.6199). Rendered, not quoted.
Two classes, exact weights, no bias:
w₀ = (3, 4) w₁ = (4, −3) — orthogonal, both of norm 5.
The Lipschitz constant of the map x ↦ logits is the spectral norm of W. Here W Wᵀ = 25·I, so both singular values are 5: L = 5, computed live, not assumed.
Live geometry for the current input:
| quantity | value |
|---|
The certified radius is m/(√2·L). Because ‖w_t − w_r‖ ≤ √2·L for any pair, this radius never exceeds the true distance to a class boundary — that inequality is the proof.
The neighbour the-fgsm runs the empirical arms race: craft ε·sign(∇) perturbations, harden, craft again — each defense only survives the attacks you happened to try.
This sphere answers that race with a proof over a region. The FGSM optimum for a linear model is exactly ε·sign(w); its minimal L2 attack is the margin along w/‖w‖. Certification takes those same closed forms and turns them inside-out: instead of finding one adversary, it rules out every adversary inside the ball. Empirical defense is the previous sphere's premise; provable defense is this one's conclusion.
The blue team's live check: independently recompute L from W, the certified radius, and the true adversarial distance, and confirm the certificate is sound (safe ball ⊆ true safe region). If red feeds an unsound bound, this badge is where it shows.
Feed the certifier a point x = (x₁, x₂). The classifier reads two logits z₀ = w₀·x and z₁ = w₁·x; the predicted class is the larger, and the margin m is the gap between them — top-1 minus top-2. Everything the certificate needs is (x, m, L).
Move the point below and the machine re-proves its safe radius on the spot.
The safe radius is m/(√2·L) with L = 5. Push the point toward the boundary and the margin — and the radius — shrink to zero.
Every number is computed from the four rows of W on the spot — logits, margin, spectral norm, radius — never looked up.
What the machine produces, proven: a certified L2 radius — around x. Claim: no perturbation with ‖δ‖₂ strictly below this radius changes the predicted class — verified by driving the worst-case direction right up to the boundary. A larger Lipschitz constant would only shrink this ball.
The blue team's witness (left) re-derives this radius live; the red team (right) tries to inflate it past the truth.
And it certifies one metric only: an L2 (or L∞) ball says nothing about rotations, blur, or a semantic edit that leaves the pixel norm large. "Certified" means "provably safe inside this ball," not "safe."
"A certified model is a robust model." Cut. It is provably robust only inside one small ball around one point — nothing is claimed elsewhere, and the ball can be tiny.
"No attack beat it, so it is certified." Cut. Survived attacks are empirical; a certificate is a proof that rules out all attacks in a region. Different thing.
"The Lipschitz constant is easy to get." Kept, corrected. Exact is NP-hard; usable bounds are loose. The guarantee is real — the tightness is the open problem.
The red team's move: hand the certifier a Lipschitz bound smaller than the true one (L = 4 < 5). The formula then claims a radius that reaches past the real boundary — a "safe" ball with a real adversarial example inside it. The blue team's witness (window 7) recomputes the true geometry and catches it.
Use an unsound bound and the certified radius overshoots the true adversarial distance — a flip lives inside the "safe" zone. The witness recomputes, disagrees, and turns red. Nothing is faked; the attack is real and it is caught.