DEV Community

Umesh Tharuka Malaviarachchi
Umesh Tharuka Malaviarachchi

Posted on

Randomized Smoothing: Why Adding Noise Can Certify Robustness

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 ff be any classifier, for example a neural network, mapping inputs to labels. Fix a noise level σ>0\sigma > 0 . The smoothed classifier gg is defined by

g(x)=arg⁡max⁡c  Pϵ∼N(0,σ2I)[f(x+ϵ)=c] g(x) = \arg\max_{c} \; \mathbb{P}_{\epsilon \sim \mathcal{N}(0, \sigma^2 I)}[f(x + \epsilon) = c]

In words: sample many noisy copies of xx , classify each one with the base classifier ff , 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 cAc_A at xx , with probability pAp_A , and suppose the runner-up class has probability at most pBp_B , where pA>pBp_A > p_B . Then the prediction is guaranteed to stay cAc_A for every perturbation δ\delta with

∣δ∣2<R=σ2(Φ−1(pA)−Φ−1(pB)) |\delta|_2 < R = \frac{\sigma}{2}\left(\Phi^{-1}(p_A) - \Phi^{-1}(p_B)\right)

where Φ−1\Phi^{-1} 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 σ\sigma 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 pAp_A approaches 1 and pBp_B 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 xx , and the noise centred at the perturbed point x+δx + \delta . Both are Gaussian with the same variance, shifted by δ\delta . 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 cAc_A drop when we shift the Gaussian by δ\delta ? The worst case, the base classifier that loses the most mass for class cAc_A , is a half-space classifier: it labels exactly the points on one side of a hyperplane as cAc_A , with the hyperplane oriented along δ\delta . 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 Φ\Phi , 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 ff , its weights, or its training procedure. It depends only on the two probabilities pAp_A and pBp_B .

The bound is also tight. The half-space classifier attains it, so no better radius can be proved from pAp_A and pBp_B 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 pAp_A and pBp_B 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 pAp_A with a Clopper-Pearson interval. Setting pB=1−pAp_B = 1 - p_A 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
Enter fullscreen mode Exit fullscreen mode

A few details matter. The classifier may abstain when the lower bound on pAp_A falls below one half; that is honest behaviour, not a failure. The radius formula here uses pB=1−pAp_B = 1 - p_A , which is the conservative choice made by most implementations, and it simplifies the radius to R=σΦ−1(pA)R = \sigma \Phi^{-1}(p_A) . 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 σ\sigma controls a direct trade-off:

  • Larger σ\sigma gives larger certified radii, because the radius is proportional to σ\sigma .
  • Larger σ\sigma also degrades clean accuracy, because the base classifier must classify heavily corrupted inputs.

On CIFAR-10, a typical smoothed classifier with σ=0.25\sigma = 0.25 keeps roughly 75 percent clean accuracy and certifies a radius of about 0.5 in ℓ2\ell_2 norm on a large fraction of test points. Push σ\sigma 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 ℓ2\ell_2 norm only. The Gaussian construction gives an ℓ2\ell_2 guarantee. An ℓ∞\ell_\infty guarantee does not follow, and converting between norms in high dimensions is costly: an ℓ2\ell_2 radius of 0.5 on a 3072-dimensional CIFAR-10 image corresponds to an ℓ∞\ell_\infty 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 ℓ1\ell_1 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 pAp_A 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 ℓ2\ell_2 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 ℓ1\ell_1 certificates, and uniform noise over a cube yields ℓ∞\ell_\infty certificates, though the radii are typically small.
  • Data-dependent smoothing: choosing σ\sigma 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 ℓ2\ell_2 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)