Randomized Smoothing

The foundational operation of randomized smoothing involves adding isotropic Gaussian noise to the input before classification. For a base classifier f and an input x, the smoothed classifier g is defined as:

g(x) = argmax_c P(f(x + ε) = c) where ε ~ N(0, σ²I)

• The noise level σ is a critical hyperparameter controlling the robustness-accuracy trade-off
• Larger σ provides stronger certification radii but degrades clean accuracy
• The noise creates a Lipschitz-continuous decision boundary, smoothing out adversarial pockets

The robustness certificate is derived from the Neyman-Pearson lemma, which provides the optimal hypothesis test between two Gaussian distributions. This yields a closed-form certified radius R:

R = σ/2 * (Φ⁻¹(p_A) - Φ⁻¹(p_B))

• p_A is the lower confidence bound of the top class probability
• Φ⁻¹ is the inverse standard Gaussian CDF
• The guarantee is probabilistic: it holds with confidence 1-α, where α is the significance level
• This is a sound certificate—if the condition holds, no adversarial example exists within the radius

At inference time, the smoothed classifier's prediction is estimated via Monte Carlo sampling rather than computed analytically:

1. Draw n samples of Gaussian noise: ε₁, ε₂, ..., εₙ ~ N(0, σ²I)
2. Compute the base classifier's prediction for each noisy copy: f(x + εᵢ)
3. Take a majority vote across the n predictions

• Typical n ranges from 10,000 to 100,000 samples for certification
• A Binomial confidence interval (Clopper-Pearson) is used to bound the true top-class probability
• The process is embarrassingly parallel and can be batched on GPUs

Randomized smoothing operates in two distinct modes with different computational budgets:

• Prediction Mode: Uses a small number of samples (e.g., n=100) to make a fast, robust prediction without computing a radius. The majority class is returned immediately
• Certification Mode: Uses a large number of samples (e.g., n=100,000) and a hypothesis test to output both a predicted class and a guaranteed ℓ₂ radius within which the prediction is provably constant

This separation allows the technique to be deployed in latency-sensitive applications while still providing formal guarantees when needed

Unlike adversarial training, randomized smoothing provides a provable guarantee that does not depend on the specific attack algorithm used:

• The certificate holds against any perturbation within the ℓ₂-ball, regardless of how it was generated
• This includes unknown, future, or adaptive attacks that specifically target the smoothing mechanism
• The only assumption is that the attacker is constrained to an ℓ₂-norm budget
• Extensions exist for ℓ₁, ℓ∞, and other norms using different noise distributions (Laplace, Uniform)
• This property makes it a gold standard for safety-critical applications where worst-case guarantees are required

Standard randomized smoothing degrades significantly on high-resolution images because Gaussian noise destroys fine details. Denoised smoothing addresses this by prepending a denoiser to the base classifier:

g(x) = argmax_c P(f(denoise(x + ε)) = c)

• The denoiser is typically a pre-trained diffusion model or a custom DnCNN
• It removes the Gaussian noise before classification, preserving image fidelity
• This dramatically improves clean accuracy while maintaining the same certification guarantees
• The denoiser itself does not need to be robust—the smoothing framework handles certification independently