Dev.to AI πŸ€– Ai πŸ‘ 0 πŸ“– 7 min read

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 de

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 f be any classifier, for example a neural network, mapping inputs to labels. Fix a noise level Οƒ>0 . The smoothed classifier g is defined by

g(x)=argcmax​Pϡ∼N(0,Οƒ2I)​[f(x+Ο΅)=c]

In words: sample many noisy copies of x , classify each one with the base classifier f , 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 cA​ at x , with probability pA​ , and suppose the runner-up class has probability at most pB​ , where pA​>pB​ . Then the prediction is guaranteed to stay cA​ for every perturbation Ξ΄ with

∣δ∣2​<R=2σ​(Ξ¦βˆ’1(pA​)βˆ’Ξ¦βˆ’1(pB​))

where Ξ¦βˆ’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 Οƒ 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 pA​ approaches 1 and pB​ 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 x , and the noise centred at the perturbed point x+Ξ΄ . 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 cA​ drop when we shift the Gaussian by Ξ΄ ? The worst case, the base classifier that loses the most mass for class cA​ , is a half-space classifier: it labels exactly the points on one side of a hyperplane as cA​ , 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 f , its weights, or its training procedure. It depends only on the two probabilities pA​ and pB​ .

The bound is also tight. The half-space classifier attains it, so no better radius can be proved from pA​ and pB​ 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 pA​ and pB​ 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 pA​ with a Clopper-Pearson interval. Setting pB​=1βˆ’pA​ 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 pA​ falls below one half; that is honest behaviour, not a failure. The radius formula here uses pB​=1βˆ’pA​ , which is the conservative choice made by most implementations, and it simplifies the radius to R=ΟƒΞ¦βˆ’1(pA​) . 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 Οƒ=0.25 keeps roughly 75 percent clean accuracy and certifies a radius of about 0.5 in β„“2​ 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 β„“2​ norm only. The Gaussian construction gives an β„“2​ guarantee. An β„“βˆžβ€‹ guarantee does not follow, and converting between norms in high dimensions is costly: an β„“2​ 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 β„“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 pA​ 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​ 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​ 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 β„“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

πŸ“° Read the original article on Dev.to AI

Originally published by Dev.to AI. Aggregated on AIWithGhost for educational purposes β€” full credit and traffic to the original publisher.