Adversarial examples are one of the most unsettling facts in machine learning. A classifier that is 95 percent accurate on clean images can be flipped by a perturbation so small that a human cannot see it. Worse, most defences against such attacks are empirical: they work until someone finds a stronger attack. Randomized smoothing is different. It turns any classifier, no matter how it was trained, into a new classifier that comes with a mathematical certificate: no perturbation smaller than a known radius can change its prediction.
This article explains how that certificate works, why the proof rests on a classical result from statistics, and where the method breaks down in practice.
The problem with empirical defences
Adversarial training, gradient masking, and input denoising all share the same weakness: they are tested against the attacks we know about. A defence that survives projected gradient descent today may fall to a different optimiser tomorrow. The history of adversarial robustness is a cycle of defence, attack, broken defence.
A certified defence breaks the cycle by proving a guarantee. Instead of saying "we could not find an attack", it says "no attack within this radius exists". Randomized smoothing achieves this with a remarkably simple construction: add Gaussian noise to the input, and take a majority vote over the noisy predictions.
The smoothed classifier
Let be any classifier, for example a neural network, mapping inputs to labels. Fix a noise level . The smoothed classifier is defined by
In words: sample many noisy copies of , classify each one with the base classifier , and return the most common label. The randomness is the whole point. Smoothing replaces a jagged decision boundary with an averaged one, and averaging over a Gaussian makes the result Lipschitz in a precise, provable sense.
In practice we cannot compute the probabilities exactly, so we estimate them with Monte Carlo sampling and a statistical test. The certificate is then probabilistic, but with a confidence level we choose, typically 99.9 percent. More on that below.
The certified radius
Suppose the smoothed classifier predicts class at , with probability , and suppose the runner-up class has probability at most , where . Then the prediction is guaranteed to stay for every perturbation with
where is the inverse of the standard Gaussian CDF. This is the central theorem of randomized smoothing, due to Cohen, Rosenfeld and Kolter (2019).
The formula has an intuitive reading. The radius grows with the noise level and with the margin between the top class probability and the runner-up probability. A confident, well-separated prediction earns a large certificate; a close call earns a small one. When approaches 1 and approaches 0, the radius grows without bound, though in practice finite sampling caps what we can certify.
Why the Neyman-Pearson lemma does the work
The proof is a beautiful application of the Neyman-Pearson lemma, the classical result that the likelihood ratio test is the most powerful test of one hypothesis against another.
Consider two distributions: the noise centred at , and the noise centred at the perturbed point . Both are Gaussian with the same variance, shifted by . The smoothed classifier's decision at each point depends on how much probability mass the base classifier assigns to each class under these two distributions.
The key question is: how much can the probability of class drop when we shift the Gaussian by ? The worst case, the base classifier that loses the most mass for class , is a half-space classifier: it labels exactly the points on one side of a hyperplane as , with the hyperplane oriented along . This is exactly what Neyman-Pearson tells us: among all sets with a given probability under the first Gaussian, the half-space minimises the probability under the shifted Gaussian.
Because the worst case is a half-space, and the Gaussian mass of a half-space shifts in a way governed by , the certified radius follows from a one-dimensional calculation. The high-dimensional problem collapses to a line. That is the elegance of the result: the certificate does not depend on the architecture of , its weights, or its training procedure. It depends only on the two probabilities and .
The bound is also tight. The half-space classifier attains it, so no better radius can be proved from and alone. Any improvement must use more information about the base classifier than its top two class probabilities.
From probabilities to a certificate in code
In practice we estimate
and
by sampling. A typical implementation has two phases. First, draw a modest number of samples, say 100, to identify the predicted class. Then draw many more, say 100,000, to estimate a lower confidence bound on
with a Clopper-Pearson interval. Setting
gives a conservative radius. The sketch below shows the core logic.
import numpy as np
from scipy.stats import norm, binomtest
def smooth_predict(f, x, sigma, n_samples, alpha=0.001):
# Phase 1: identify the top class with a small sample
noise = np.random.randn(100, *x.shape) * sigma
votes = [f(x + e) for e in noise]
top_class = max(set(votes), key=votes.count)
# Phase 2: lower confidence bound on p_A
noise = np.random.randn(n_samples, *x.shape) * sigma
count = sum(1 for e in noise if f(x + e) == top_class)
p_a_lower = binomtest(count, n_samples, alternative="greater").proportion_ci(
confidence_level=1 - alpha
).low
if p_a_lower < 0.5:
return None, 0.0 # abstain: cannot certify
radius = sigma * norm.ppf(p_a_lower) # using p_B = 1 - p_A
return top_class, radius
A few details matter. The classifier may abstain when the lower bound on falls below one half; that is honest behaviour, not a failure. The radius formula here uses , which is the conservative choice made by most implementations, and it simplifies the radius to . And the whole procedure assumes the base classifier was trained with Gaussian noise augmentation, otherwise its accuracy under noise collapses and the certificate is worthless.
The accuracy-robustness trade-off
Randomized smoothing is not free. The noise level controls a direct trade-off:
- Larger gives larger certified radii, because the radius is proportional to .
- Larger also degrades clean accuracy, because the base classifier must classify heavily corrupted inputs.
On CIFAR-10, a typical smoothed classifier with keeps roughly 75 percent clean accuracy and certifies a radius of about 0.5 in norm on a large fraction of test points. Push to 1.0 and the certified radii grow, but clean accuracy falls toward 50 percent. There is no noise level that gives both state-of-the-art accuracy and large certificates.
This trade-off is not an artefact of the method; it reflects something real. A classifier that is robust to large perturbations must ignore fine-grained features, and fine-grained features are part of what makes clean accuracy high. Training with noise augmentation, or with consistency regularisation across noisy copies, softens the trade-off but does not remove it.
Limitations and common pitfalls
The certificate is in norm only. The Gaussian construction gives an guarantee. An guarantee does not follow, and converting between norms in high dimensions is costly: an radius of 0.5 on a 3072-dimensional CIFAR-10 image corresponds to an radius of only about 0.009 per pixel. Other noise distributions give other norms, but each comes with its own trade-offs, and Laplace noise for is the most common alternative.
The certificate is per-input, not global. Some inputs certify well, others barely at all. Reporting an average certified radius hides the distribution. The standard metric is certified accuracy at a given radius: the fraction of test points that are both correctly classified and certified at that radius.
Sampling cost is real. Certifying a single ImageNet image with 100,000 samples means 100,000 forward passes. That is expensive at inference time and prohibitive for real-time use. Faster certification via deterministic approximations or fewer samples with looser bounds is an active research area.
The base classifier must be noise-trained. Applying smoothing to a classifier trained only on clean data gives tiny values of and useless radii. The method works because noise augmentation during training teaches the base classifier to be stable under the same noise used for smoothing. Smoothing a model after the fact is not a shortcut.
Do not confuse the certificate with the attack surface. The guarantee covers perturbations of the input within the ball. It says nothing about poisoned training data, backdoors, or distribution shift. A certified classifier can still be wrong for the ordinary reasons classifiers are wrong.
Extensions worth knowing
- Other noise distributions: Laplace noise yields certificates, and uniform noise over a cube yields certificates, though the radii are typically small.
- Data-dependent smoothing: choosing per input, larger where the classifier is confident and smaller where it is not, can improve the accuracy-robustness frontier.
- Randomized smoothing for structured outputs: the same idea extends to segmentation and detection, where the certificate applies to the output at each pixel or region.
- Deterministic smoothing: replacing Monte Carlo sampling with analytic bounds on specific architectures removes the sampling cost but only applies to restricted model classes.
Takeaway
Randomized smoothing is the rare robustness method that is both simple to implement and mathematically airtight. Add Gaussian noise, take a majority vote, and the Neyman-Pearson lemma hands you a certified radius that no attack within that radius can break. The price is real: lower clean accuracy, heavy sampling cost, and a guarantee that only covers perturbations. But when the requirement is a proof rather than a hope, that price is often worth paying. In safety-critical settings, knowing exactly how much robustness you have is more valuable than having more of it unmeasured.
Connect with me on LinkedIn: linkedin.com/in/umeshtharukaofficial
Top comments (0)