Adversarial robustness is usually narrated as a fight scene.

The attacker chooses a small perturbation. The model changes its mind. The defender patches the training procedure. The attacker adapts.

Randomized smoothing changes the tone. It does not ask whether today’s attack has been found. It asks for a certificate:

inside this ball, the prediction cannot change

That is a different kind of claim: local, probabilistic, and geometric. It does not say the classifier is globally safe. It does not say the base model is wise. It says that, around one input, a particular Gaussian vote has enough probability margin to certify an \(\ell_2\) radius.

The object being certified is not the original classifier \(f\). It is the smoothed classifier

\[g(x) = \arg\max_c P(f(x + \epsilon)=c), \quad \epsilon \sim \mathcal{N}(0,\sigma^2 I).\]

Run the base classifier on many noisy copies of the same input. Count the votes. If class \(A\) wins by enough, the smoothed classifier predicts \(A\).

The surprising part is that a vote gap can become a radius.

The Radius Hides in a Gaussian Tail

Suppose the top class has probability \(p_A\) under Gaussian noise, and the runner-up has probability \(p_B\). Cohen, Rosenfeld, and Kolter proved a tight \(\ell_2\) robustness guarantee for Gaussian randomized smoothing:1

\[R = \frac{\sigma}{2} \left( \Phi^{-1}(p_A) - \Phi^{-1}(p_B) \right),\]

where \(\Phi^{-1}\) is the inverse standard normal CDF.

For binary classification, \(p_B = 1-p_A\), so this simplifies to

\[R = \sigma \Phi^{-1}(p_A).\]

If the smoothed classifier says class \(A\) and \(\|\delta\|_2 < R\), then the smoothed classifier also says class \(A\) at \(x+\delta\).

The theorem is not about gradients. It is not about a particular attack. It is about how much a Gaussian measure can shift when its center moves. The proof uses a Neyman-Pearson style argument: among all regions with a given Gaussian mass, halfspaces are the worst case for losing mass under a shift. If class \(A\) owns enough probability mass at \(x\), then no perturbation smaller than the radius can make some other class overtake it.

That is the shape to keep in your head:

large noisy vote gap -> certified L2 ball

The catch is that in real models we do not know \(p_A\) exactly. We estimate it with Monte Carlo samples and certify from a lower confidence bound, not from the raw vote fraction. The lab below does the same thing. It uses a 99% Wilson lower bound for the top-class vote before converting the vote to a radius. That is still a toy certificate, but it avoids pretending that 768 noisy votes are an oracle.

A Noisy Polling Booth

The base classifier in the lab is deliberately ugly: a two-dimensional decision boundary with high-frequency wiggles. The smoothed classifier votes by adding Gaussian noise around the red point. The orange circle is the conservative certificate radius. The dashed red circle is a brute-force search for the nearest smoothed-boundary flip that the lab could find.

Blue class Green class Test point / found flip Conservative certificate

Deterministic synthetic experiment. The smoothed probability is estimated with Gaussian votes. The displayed radius uses a 99% Wilson lower bound on the top vote before applying the binary randomized-smoothing formula.

With the default settings, the raw top-class vote is about 59.4%. The 99% lower-bound vote is about 54.7%, so the displayed radius is only 0.054 instead of the ideal-formula radius 0.107 you would get by pretending the raw Monte Carlo vote were exact. A brute-force search finds the nearest smoothed boundary around 0.162, outside the conservative certificate.

That gap is the healthy shape:

conservative certificate < searched boundary

Try increasing Noise sigma. The boundary gets smoother, but the top vote can also fall toward 50%. A larger noise scale does not automatically give a larger certificate. The formula multiplies by \(\sigma\), but it also asks whether the noisy vote still has a margin.

Try increasing Boundary wiggle or Wiggle frequency. The base classifier becomes more brittle. Smoothing can wash out small wiggles, but if the red point is near a folded region, the vote gap shrinks and the certified radius collapses.

This is the essential trade:

noise removes small brittle features
noise also asks the classifier to be right under corrupted inputs

Read the Certificate Literally

The first adversarial-example papers made the vulnerability feel almost paradoxical: imperceptible perturbations could flip the prediction of high performing neural networks.2 Goodfellow, Shlens, and Szegedy argued that high-dimensional linear behavior is enough to explain much of the phenomenon and introduced the fast gradient sign method as a simple attack construction.3

Randomized smoothing does not make that history go away. It changes the noun in the claim.

It does not certify the base classifier \(f\). The base classifier in the lab still has tiny folds. The certificate belongs to \(g\), the classifier that votes over Gaussian perturbations.

It does not certify every input. If the noisy vote is close to 50%, the radius is zero or tiny. Smoothing can abstain in practice by refusing to certify when the vote is too uncertain.

It does not prove semantic robustness. An \(\ell_2\) ball is a mathematical threat model. Whether that ball matches the perceptual, physical, or product risk depends on the domain.

And it does not let us ignore estimation. Cohen et al.’s practical certification procedure samples the base classifier many times and uses statistical confidence bounds for class probabilities.1 The theorem needs probabilities; code gets counts.

Why the Trick Scaled

PixelDP had already drawn a connection between randomized mechanisms, differential privacy, and adversarial robustness certificates.4 The Cohen-Rosenfeld-Kolter result became especially influential because Gaussian smoothing gave a tight \(\ell_2\) certificate and could wrap arbitrary base classifiers.

That wrapper property matters. You can train a large classifier to be accurate under Gaussian noise, then certify the smoothed version. Salman et al. improved the empirical side by adversarially training smoothed classifiers, showing that training for the smoothed objective can materially improve certified accuracy.5

The later literature also generalizes the geometry. Gaussian smoothing is tied to \(\ell_2\) balls. Other smoothing distributions can certify other shapes, but the analysis is not free. Yang et al.’s “all shapes and sizes” work is a good example of asking what randomized smoothing can and cannot certify under other norms.6

The lab stays in two dimensions because the geometry is visible. The same pressure exists in images, embeddings, sensor vectors, and tabular models:

to certify a region, the noisy vote must dominate throughout the region

The Polling-Place Picture

I find randomized smoothing easiest to remember as a polling place.

The base classifier is not asked once. It is asked many times under nearby Gaussian worlds. If one class wins by a large enough margin, moving the polling center a little cannot make the other class win. The certified ball is the set of centers for which the winner is mathematically locked in.

The certificate is beautiful because it is attack-independent.

It is limited because it is vote-dependent.

That tension is the whole subject. Random noise does not make models robust by itself. Random noise gives us a measurable probability gap. Sometimes that gap is wide enough to draw a ball.

  1. Jeremy Cohen, Elan Rosenfeld, and Zico Kolter, “Certified Adversarial Robustness via Randomized Smoothing”, ICML 2019. ↩ ↩2

  2. Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus, “Intriguing Properties of Neural Networks”, arXiv 2013. ↩

  3. Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy, “Explaining and Harnessing Adversarial Examples”, ICLR 2015. ↩

  4. Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana, “Certified Robustness to Adversarial Examples with Differential Privacy”, IEEE Symposium on Security and Privacy 2019. ↩

  5. Hadi Salman, Greg Yang, Jerry Li, Pengchuan Zhang, Huan Zhang, Ilya Razenshteyn, and Sebastien Bubeck, “Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers”, NeurIPS 2019. ↩

  6. Greg Yang, Tony Duan, J. Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li, “Randomized Smoothing of All Shapes and Sizes”, ICML 2020. ↩