Randomized Smoothing

Unlike empirical defenses, randomized smoothing provides a mathematical guarantee that a prediction will remain constant for any input within a certified L2 radius. The certification radius R is computed using the formula: R = σ/2 * (Φ⁻¹(pA) - Φ⁻¹(pB)), where σ is the noise level, pA and pB are the top two class probabilities under the smoothed distribution, and Φ⁻¹ is the inverse Gaussian CDF. This guarantee is attack-agnostic—it holds against all possible adversaries, not just gradient-based methods.

The core mechanism constructs a smoothed classifier g(x) that returns the most likely prediction when Gaussian noise is added to the input:

• Base classifier f: Any arbitrary model (neural network, decision tree, etc.)
• Noise distribution: Isotropic Gaussian N(0, σ²I) with standard deviation σ
• Smoothed prediction: g(x) = argmax_c P(f(x + ε) = c) where ε ~ N(0, σ²I)

The noise level σ acts as a tunable robustness-accuracy trade-off parameter. Larger σ yields larger certified radii but may degrade clean accuracy.

Certification at inference time requires estimating the prediction probabilities under noise through statistical sampling:

• Prediction phase: Draw n₀ samples of Gaussian noise, compute the majority class ĉ
• Certification phase: Draw n samples, count occurrences of ĉ to estimate lower bound pA with confidence 1-α
• Sample counts: Typically n₀ = 100 and n = 100,000 for tight certification bounds
• Clopper-Pearson confidence interval: Used to compute a rigorous lower bound on the true probability

The procedure is computationally expensive at inference time but provides rigorous statistical guarantees.

The theoretical foundation of randomized smoothing rests on the Neyman-Pearson lemma from statistical hypothesis testing. For binary classification with Gaussian noise, the optimal adversary is constrained by the likelihood ratio between two shifted Gaussian distributions. The worst-case classifier—one that minimizes certified radius for a given pA—is a linear classifier defined by a half-space. This connection to classical statistics provides the tightness of the L2 certification bound, making it the gold standard for provable defenses.

Randomized smoothing operates as a wrapper around any base classifier, making it uniquely flexible:

• No architectural constraints: Works with CNNs, ResNets, Vision Transformers, or any differentiable model
• No retraining required: Can be applied post-hoc to pre-trained models, though performance improves with noise-augmented training
• Black-box compatibility: The base model can be treated as an oracle; only query access is needed
• Composability: Can be combined with other defenses like adversarial training for enhanced empirical robustness

This agnosticism makes it immediately deployable on existing production models.

Despite its theoretical elegance, randomized smoothing has notable constraints:

• L2 norm only: Standard formulation certifies only against L2-bounded perturbations, not L∞ or L1 attacks
• Scalability challenges: Certification requires tens of thousands of forward passes per input
• Semantic blind spot: The guarantee is purely geometric; it does not account for perceptual similarity
• Noise-level sensitivity: σ must be chosen before deployment; mismatched σ leads to loose or invalid certificates
• Variance in estimation: Finite sampling introduces statistical error, requiring careful confidence level calibration

A property of a model that provides a mathematical guarantee that its prediction will not change for any input within a specified Lp-norm radius. Unlike empirical defenses that can be broken by stronger attacks, certified methods like randomized smoothing offer provable lower bounds on the magnitude of perturbation required to flip a classification. This is crucial for safety-critical applications where worst-case guarantees are non-negotiable.

The core mechanism of randomized smoothing involves constructing a smoothed classifier by adding isotropic Gaussian noise to the input. The prediction becomes the argmax of the class probabilities under this noise distribution. This process effectively 'smooths out' the decision boundary, transforming a potentially sharp, brittle base classifier into a provably robust one. The standard deviation of the noise is a critical hyperparameter controlling the robustness-accuracy trade-off.

To estimate the prediction of the smoothed classifier, randomized smoothing relies on Monte Carlo sampling. The algorithm makes N noisy copies of the input and queries the base classifier on each. The final prediction is the majority vote. To provide a high-confidence guarantee, techniques like the Clopper-Pearson confidence interval or Hoeffding's inequality are used to bound the true probability of the top class from the empirical counts.

An extension that applies randomized smoothing to a pipeline including a denoiser (often a pre-trained neural network) before the base classifier. This allows the use of smoothing on classifiers not originally trained with heavy noise augmentation. The denoiser attempts to remove the added Gaussian noise, improving the accuracy of the base classifier on the noisy inputs and leading to a higher certified accuracy at a given radius.

A training methodology that complements randomized smoothing by enforcing that the base classifier's predictions on different noisy versions of the same clean input are consistent. This is often achieved by minimizing a divergence metric like KL divergence between the softmax outputs. This directly optimizes the base model for the smoothing process, leading to tighter certification bounds and higher certified accuracy.