Randomized smoothing
Randomized smoothing is a method for constructing a certifiably robust classifier by averaging the predictions of a base classifier under random perturbations of its input. The resulting smoothed classifier possesses a mathematically verified region around each certified input within which its prediction cannot change. For isotropic Gaussian perturbations, this region is a ball measured by the Euclidean norm.
The method separates empirical resistance to adversarial examples from certified robustness. Empirical resistance records whether particular attacks find a prediction-changing perturbation, whereas a certificate establishes the absence of any such perturbation inside a specified set. The guarantee applies to the smoothed classifier rather than directly to the base classifier, whose decision boundary may remain irregular or otherwise analytically inaccessible.
Mathematical formulation
Let
[ f:\mathbb{R}^{d}\rightarrow \mathcal{Y} ]
be a base classifier with a finite label set (\mathcal{Y}). Given a random vector (\varepsilon) drawn from a fixed probability distribution, the corresponding smoothed classifier is
[ g(x)=\operatorname*{arg,max}_{c\in\mathcal{Y}} \Pr!\left(f(x+\varepsilon)=c\right). ]
Thus, (g) assigns the class occupying the greatest probability mass under a translated noise distribution centered at (x). The definition imposes few structural conditions on (f). It can represent a neural network, a decision rule assembled from several models, or another measurable classifier.
The most widely studied construction uses isotropic Gaussian noise,
[ \varepsilon\sim\mathcal{N}(0,\sigma^{2}I), ]
where (\sigma>0) controls the scale of smoothing and (I) is the identity matrix. For a fixed input (x), let (A) denote the most probable class under this distribution. Suppose its probability satisfies
[ \Pr(f(x+\varepsilon)=A)\geq p_A, ]
while every competing class has probability at most (p_B), with (p_A>p_B). The smoothed classifier then predicts (A) for every perturbed input (x+\delta) satisfying
[ \lVert\delta\rVert_2<R, ]
where
[ R=\frac{\sigma}{2} \left( \Phi^{-1}(p_A)-\Phi^{-1}(p_B) \right) ]
and (\Phi^{-1}) is the inverse cumulative distribution function of the standard normal distribution. This radius is a pointwise guarantee because it depends on the class probabilities associated with the particular input being certified.
When only the leading-class probability is bounded and (p_A>1/2), the combined probability of all other classes is at most (1-p_A). Substitution into the general expression gives the commonly used certificate
[ R=\sigma\Phi^{-1}(p_A). ]
This simplified form can be more conservative than a certificate that separately estimates the probability of the most competitive alternative class.
Statistical and geometric basis
The Gaussian certificate follows from the Neyman–Pearson lemma. Under a displacement (\delta), the original Gaussian measure (\mathcal{N}(x,\sigma^2I)) and the shifted measure (\mathcal{N}(x+\delta,\sigma^2I)) have a likelihood ratio whose level sets are half-spaces orthogonal to (\delta). Among all measurable regions with a fixed probability under the original measure, these half-spaces attain the extremal probability under the shifted measure.
Each class of the base classifier determines a measurable decision region. The Neyman–Pearson argument bounds how much Gaussian probability that region can lose or gain after the center of the distribution moves. Applying the lower bound to the predicted class and the upper bound to its competitors yields the certified radius. This derivation does not require the decision regions themselves to be convex, smooth, or connected.
The geometry of the certificate depends on the smoothing distribution. Isotropic Gaussian noise produces an (\ell_2) guarantee because the divergence between two equally dispersed Gaussian distributions depends on the Euclidean distance between their means. Other noise distributions produce certificates associated with different perturbation sets, although the resulting bounds need not share the tight half-space characterization of the Gaussian case.
Historical development
Random perturbation had long been used in signal processing, ensemble prediction, and statistical regularization before it became a framework for certified adversarial robustness. In 2018, Mathias Lécuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana connected randomized prediction with differential privacy in the PixelDP framework. Their analysis converted stability properties of randomized computations into robustness guarantees for classification.
During the same period, Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin derived robustness bounds through Rényi divergence. These divergence-based approaches established the general relation between distributional stability and certified predictions, although their Gaussian bounds were not always tight.
In 2019, Jeremy Cohen, Elan Rosenfeld, and J. Zico Kolter gave the standard tight certificate for classifiers smoothed with isotropic Gaussian noise. Their formulation treated the base classifier as an arbitrary measurable function and reduced certification to bounds on class probabilities. The analysis also established tightness under the available probability information: without additional assumptions about the base classifier, a larger universal radius cannot be inferred from the same values of (p_A) and (p_B).
A 2020 treatment by You Watanabe expressed anisotropic Gaussian smoothing through likelihood-ratio acceptance regions and related the resulting certificates to ellipsoidal perturbation sets. For noise with covariance matrix (\Sigma), the associated displacement is measured by the Mahalanobis quantity
[ \lVert\delta\rVert_{\Sigma^{-1}}
\sqrt{\delta^{\mathsf T}\Sigma^{-1}\delta}. ]
This formulation made explicit that covariance selection changes the orientation and relative axis lengths of the certified region rather than merely changing a scalar noise level.
Hadi Salman, Greg Yang, Jerry Li, Pengchuan Zhang, Huan Zhang, Ilya Razenshteyn, and Sébastien Bubeck subsequently examined adversarially informed training of smoothed classifiers. Their SmoothAdv formulation optimized the base classifier against perturbations of its noise-averaged loss, linking randomized smoothing to adversarial training.
Certification by probability estimation
For modern classifiers, the class probabilities defining (g(x)) are generally unavailable in closed form. They are represented by expectations over the smoothing distribution and are therefore estimated by Monte Carlo method. Repeated noisy evaluations of the base classifier produce class counts governed by a multinomial distribution.
A certificate requires confidence bounds rather than raw frequency estimates. If class (A) appears (k) times among (n) independent samples, an exact lower confidence bound for its probability can be obtained from the binomial distribution, commonly through a Clopper–Pearson interval. When this lower bound does not exceed one half, the standard single-class Gaussian procedure abstains because the observations do not statistically establish that (A) has greater probability than all alternatives combined.
The confidence level is distinct from the robustness radius. The radius describes a deterministic property of the ideal smoothed classifier conditional on valid probability bounds, while the confidence level controls the probability that Monte Carlo sampling produces an invalid bound. Larger sample counts narrow the statistical interval and can increase the reported radius when the underlying leading-class probability is sufficiently high. They do not alter the mathematical definition of the smoothed classifier.
Prediction and certification also have different computational roles. Approximate prediction identifies the class with the greatest estimated noisy probability, whereas certification additionally establishes a statistically valid separation between that class and its competitors. A classifier may therefore return an ordinary smoothed prediction for an input while declining to attach a nonzero certified radius.
Training and robustness behavior
A base classifier trained only on unperturbed data can lose accuracy when evaluated under substantial Gaussian noise. Training with noise augmentation instead minimizes an expected loss of the form
[ \mathbb{E}{(x,y)} \mathbb{E}{\varepsilon} \left[ \mathcal{L}(F(x+\varepsilon),y) \right], ]
where (F) produces class scores and (\mathcal{L}) is a classification loss. This objective encourages consistent behavior throughout regions receiving appreciable probability under the smoothing distribution.
Adversarially informed smoothing objectives additionally consider input displacements within the loss evaluated under noise. Their purpose is to shape the noisy class probabilities so that the correct class retains a larger probability margin near the training data. The resulting certificate still follows from the smoothing theorem; the training objective affects the values of the probabilities rather than the validity of the theorem.
The noise scale creates a characteristic accuracy–radius relationship. Increasing (\sigma) multiplies the radius associated with fixed standardized probabilities, but it can also reduce the leading-class probability by averaging across semantically or statistically distinct regions. Consequently, a larger smoothing variance does not imply a larger realized certificate for every input.
Scope and limitations
Randomized smoothing certifies the prediction of the smoothed classifier against perturbations in a mathematically specified norm. It does not establish that all points inside the certified region preserve human-perceived meaning, nor does it certify invariance to transformations outside the modeled perturbation set. Spatial transformations and changes in illumination, for example, require separate mathematical representations before comparable guarantees can be formulated.
The certificate is local to an input and does not directly characterize global properties of the decision boundary. Two nearby inputs may receive substantially different radii because their Gaussian class probabilities differ. Certification can also require many evaluations of the base classifier, especially when a narrow confidence interval is needed or when the leading probability lies near the threshold for abstention.
The guarantee remains valid regardless of whether an attack algorithm is available. Conversely, failure to obtain a positive radius does not establish the existence of an adversarial example. It establishes only that the selected probability bounds and smoothing theorem do not certify a larger region for that input.
High-dimensional behavior depends on the relationship among data geometry, classifier margins, and the chosen noise distribution. An isotropic Gaussian perturbs every coordinate, so its total displacement typically grows with dimension even when the per-coordinate variance remains fixed. This effect can reduce clean accuracy on data concentrated near a lower-dimensional structure, while anisotropic smoothing replaces spherical symmetry with a covariance-dependent geometry.