Certified robustness that scales — not by bounding a network's Lipschitz constant, but by drowning it in Gaussian noise and counting votes. If the majority class survives noise of std σ with probability pA, the smoothed classifier carries a hard, closed-form L2 certificate: no perturbation smaller than R = σ·Φ-1(pA) can change its answer. Noise, turned into a proof.
SOURCE Cohen, Rosenfeld & Kolter, Certified Adversarial Robustness via Randomized Smoothing (2019) — arxiv.org/abs/1902.02918. Rendered, not quoted.
A base classifier f is smoothed into g: to classify x, sample x + ε, ε ~ N(0, σ²I), and return the majority vote. Let pA be the probability the top class wins under that noise.
Theorem. g is constant inside the L2 ball of radius R = σ·Φ-1(pA) around x. No attack of L2 norm < R flips it.
Here Φ-1 is the inverse standard-normal CDF (a probit). The bound is tight: an adversary that only knows pA can force a flip at exactly R.
Ground truth is a constructed linear base f(x)=sign(w·x), w=[3,4], evaluated at x=[2,1]. Every quantity below is closed-form.
Neighbour: the-certified-robustness — the Lipschitz-bound school (IBP, CROWN, Reluplex) that proves a no-attack zone by bounding how fast the network can change.
Smoothing pays a different price. It needs no Lipschitz constant and no access to weights — it works on models far too big to bound, at the cost of noise-time inference and a sampling estimate of pA. A probabilistic no-attack zone where a deterministic one was impossible.
Live re-check of the load-bearing identity R = σ·Φ-1(pA) against the linear model's exact margin, probed at a noise level σ=2 ≠ 1 so a dropped factor cannot hide.
Green only while the certificate scales with σ. Trip THE TAMPER (window 6) and this flips red on the spot.
The noise level and the measured top-class probability:
Preset from the linear base at σ=1: pA=Φ(w·x / (σ ∥w∥)) = Φ(2) ≈ 0.9772.
For the linear base the certificate is exact: smoothing recovers the true distance to the decision boundary. pA→1 ⇒ R→∞; pA=0.5 ⇒ R=0 (a coin flip certifies nothing).
At σ=1, pA=Φ(2) the smoothed classifier is certifiably unflippable inside R=2.0000 in L2 — and this equals the linear base's exact margin, so the bound is met with no slack. Raise σ and R grows for the same pA: noise buys certified radius, trading clean accuracy for it.
δ = −margin·w/∥w∥ = [−1.2,−1.6], norm exactly 2.0 — it reaches the boundary at precisely R, never sooner. But switch norms: the optimal L∞ attack ε·sign(w) flips the base at ε = margin / ∥w∥1 = 10/7 ≈ 1.43, whose L2 norm is only 1.43√2 ≈ 2.02 — barely outside, and an L∞ certificate here does not follow from the L2 one.
Gaussian smoothing certifies L2 and L2 alone. Other threat models need other noise (uniform / Laplacian) — and weaker guarantees.
“A high certified accuracy means the model is actually that robust.”
→ It means robust with confidence 1−α from a Monte-Carlo estimate of pA. The certificate is probabilistic; a lower-confidence-bound on pA must be used or the radius over-claims. AMBER
“Bigger σ is strictly better — free robustness.”
→ Bigger σ enlarges R for a fixed pA, but it also drives pA down (the base sees noisier inputs), collapsing clean accuracy. The trade is real.
“Φ-1(1) is a big number.”
→ It is +∞. A never-wrong class is certified everywhere — which is exactly why the estimate never returns pA=1 from finite samples.
Disclosed planted void: drop the σ factor and report R = Φ-1(pA). It looks fine at σ=1 and over-claims for small σ. THE WITNESS (7) probes at σ=2 and catches it.