Randomized Smoothing

The core process transforms a base classifier f into a smoothed classifier g. For any input x, g(x) returns the class that f is most likely to predict when x is perturbed by isotropic Gaussian noise with variance σ². This creates a statistical barrier: an adversary must overcome the noise distribution to change the prediction, not just cross a single decision boundary. The prediction is computed via Monte Carlo sampling, repeatedly querying f on noisy copies of x and taking a majority vote.

The defining property of randomized smoothing is a provable L2-radius around the input. If the smoothed classifier predicts class cA with probability pA, and the runner-up class cB has probability pB, the prediction is guaranteed to remain constant for any adversarial perturbation with an L2-norm less than:

• R = (σ/2) * [Φ⁻¹(pA) - Φ⁻¹(pB)]

where Φ⁻¹ is the inverse Gaussian CDF. This radius is a lower bound on true robustness, meaning the model is at least this robust, often more. The guarantee is probabilistic, holding with a configurable confidence level α (typically 99.9%).

The practical algorithm operates in two phases:

• PREDICT: Sample n noisy copies of the input, query the base classifier, and return the plurality class. If the top class count is insufficient, abstain.
• CERTIFY: Sample n₀ copies to identify the most likely class, then sample n additional copies to compute a lower confidence bound on its probability using a Clopper-Pearson binomial confidence interval. If the lower bound exceeds 0.5, compute and return the certified radius.

This decoupling allows prediction to be fast while certification uses more compute for rigorous guarantees.

Randomized smoothing is a wrapper method that treats the base classifier as a black box. It requires no knowledge of the model's architecture, weights, or training procedure. This provides three critical advantages:

• Model Flexibility: Works with any classifier, including deep neural networks, random forests, and support vector machines.
• No Retraining Required: Can be applied to pre-trained, off-the-shelf models without modification.
• Composability: Smoothing can be combined with other defenses like adversarial training to boost both empirical and certified robustness simultaneously.

The trade-off is that the base classifier must be robust to Gaussian noise, which may require specialized training for optimal performance.

Despite its formal guarantees, randomized smoothing has known limitations:

• L2-Norm Only: The standard guarantee applies only to perturbations bounded in L2-distance. Extensions exist for L1 and L∞ norms but require different noise distributions (Laplace, Uniform).
• Information Leakage: The certification procedure reveals the exact probability pA, which an adaptive attacker can exploit to craft tighter attacks than the certified radius suggests.
• Curse of Dimensionality: In high-dimensional input spaces (e.g., ImageNet-scale images), the certified radius shrinks relative to the data scale, limiting practical guarantees.
• Semantic Perturbations: Smoothing does not defend against non-norm-bounded changes like rotation, translation, or lighting shifts.

A key extension addresses the base classifier's sensitivity to Gaussian noise. Denoised smoothing prepends a custom-trained denoiser before the base classifier:

• The denoiser is trained to reconstruct clean images from noisy inputs using a mean squared error loss.
• At inference, noisy inputs pass through the denoiser first, then the base classifier.
• This dramatically improves the base classifier's accuracy under noise, enabling larger σ values and thus larger certified radii.
• The denoiser can be a standard autoencoder, DnCNN, or a diffusion-based model.

This approach bridges the gap between standard accuracy and certified robustness, achieving state-of-the-art results on CIFAR-10 and ImageNet.