Randomized smoothing

Overview

Randomized smoothing replaces a function with its average over random input noise. The average is smoother than the original, and because the noise is known, one can bound how far the output can move. The wiki has two uses so far that share this core.

In the first, the smoothed classifier gives a certified prediction: the label is guaranteed to stay the same for any change inside a stated radius. The classic setting is test-time (evasion) perturbations 2003.08904 §1 2003.08904 §2.2. The smoothed classifier is the probability, over noise draws, that the base classifier outputs each label, and the prediction is the most probable label 2003.08904 §4.1.1 eq. 5 eq. 6. A certificate holds when the top class has probability at least p_A, every other class at most p_B < p_A, and a Neyman-Pearson-style condition on the two distributions is met 2003.08904 §4 eq. 9 eq. 10. The RAB paper moves the noise into the training set as well, which covers training-time backdoor triggers 2003.08904 §4.1.1.

In the second, the same averaging gives usable slopes through a non-smooth contact model, which planners and trajectory optimisers can use. This use produces no certificate 2206.10787 §2.1 2206.10787 §2.3.

Variants

Training-set smoothing for backdoor certificates (DNN)

Each training example gets fresh Gaussian noise, one model is trained per noisy copy, and each model keeps a fixed test-time noise vector that is added to inputs at inference 2003.08904 §6.1.1 alg. 1. At test time the label counts over the models give p_A and p_B from confidence bounds. For a single trigger pattern of L2 norm ‖δ‖₂ on r poisoned samples, the certificate is

\|\delta\|_2 < \frac{\sigma}{2\sqrt{r}} \left( \Phi^{-1}(p_A) - \Phi^{-1}(p_B) \right)

2003.08904 §5.1.2 eq. 13. The model abstains when p_A ≤ p_B or the radius falls below the trigger norm alg. 2. Card: RAB: Provable Robustness Against Backdoor Attacks.

Reported results, author-reported: certified accuracy 23.1-24.1% on MNIST, 24.1-24.5% on CIFAR-10 and 9.2-15.9% on ImageNette, with trigger norm 0.1 for all attacks 2003.08904 tab. 1 2003.08904 §7.1.5. Benign accuracy on CIFAR-10 falls by about 2.6 to 3.7 points against the vanilla model 2003.08904 tab. 1. Abstention rates are 1.9-6.0% 2003.08904 app. C.6.

Caveats:

• The method trains N full models. The paper uses N = 1000 for MNIST and CIFAR-10 and N = 200 for ImageNette 2003.08904 §7.1.2. Certifying one input takes N forward passes 2003.08904 §9.
• The radius shrinks with the square root of the poisoned count 2003.08904 §5.1.2. The table numbers do not say which r was used 2003.08904 tab. 1.
• Per-model test-time noise matters: on MNIST one-pixel, certified accuracy is 12.7% without it and 23.5% with it 2003.08904 app. C.5.

Exact smoothing for K-nearest-neighbour classifiers

For a KNN classifier that uses squared Euclidean distance quantised into L similarity levels, the Gaussian-smoothed prediction can be computed exactly, with no sampling 2003.08904 §6.2 [thm. 3]. The cost is O(K^(2+C) · n² · L · C) for C classes and n training points 2003.08904 app. B. Reported certified accuracy on Spambase with K=3 and σ=0.5 is 33.3-41.7% 2003.08904 tab. 2, and certifying one input takes 2.5 s 2003.08904 §7.3. The paper's linear-time claim for K=1 is not derived in its appendix 2003.08904 app. B.1. The released code runs K=1 only, so the K=3 numbers cannot be reproduced from it (see the card's "Paper vs code").

Smoothing a contact model for gradients (no certificate)

The smoothed map f_ρ(x) = E[f(x + w)] is C¹ when the noise density is C¹ 2206.10787 §2.1. Three estimators give the local linear model used by the planner 2206.10787 §2.2 2206.10787 §2.3:

• Analytic. Differentiate a closed-form smoothed map. For the contact problem, a log-barrier replaces the hard constraints, with a weight κ that rises over the iterations 2206.10787 §4.2 2206.10787 §5.1. For a 1-D frictionless cart it equals randomized smoothing with a heavy-tailed elliptical density 2206.10787 §4.3. The authors report similar results on frictional examples, without a proof 2206.10787 fig. 5.
• First-order randomized. Average the Jacobians of f at sampled points. This needs f to be locally Lipschitz 2206.10787 §2.3.
• Zero-order randomized. A score-function estimate that uses only function values, so it works for discontinuous f. It is unbiased but noisier 2206.10787 §2.3.

Minimum iMPC cost over iterations, author-reported 2206.10787 tab. 2:

On the RRT planner, the analytic variant ran faster than both randomized variants on all six tasks 2206.10787 tab. 3. The zero-order RRT row cannot be reproduced from the released code, and the paper reports no success rates 2206.10787 §8.1. Card: Smoothing contact models for planning.

When to use which

Certified coverage is low on the image benchmarks: the best reported DNN certified accuracy is 24.5%, so the DNN variant suits settings where a low-coverage guarantee is acceptable 2003.08904 tab. 1. The contact numbers come from three iMPC tasks with five trials and from six RRT tasks, on the authors' own setup 2206.10787 §5.2 2206.10787 §8.1.

Implementation sketch

Both uses rely on the same Monte Carlo average. The certification step and the gradient step differ at the end.

# Certified prediction for one input  [arxiv:2003.08904 §6.1.2] [alg. 2]
# Input:  x, models h_k with fixed noise u_k, sigma, r, trigger norm d
# Output: predicted label, or ABSTAIN

def certify(x, models, u, sigma, r, d, alpha):
    # Each model labels x plus its own fixed noise  [§6.1.2]
    counts = tally([h(x + u_k) for h, u_k in zip(models, u)])
    # Most and second most frequent labels  [alg. 2]
    top, runner_up = two_largest(counts)
    # p_A lower bound, p_B upper bound: p_B must bound every other class  [§4] [eq. 9]
    p_a = lower_bound(counts[top], len(models), alpha)
    p_b = upper_bound(counts[runner_up], len(models), alpha)
    if p_a <= p_b:
        return ABSTAIN
    # Radius for r poisoned samples  [§5.1.2] [eq. 13]
    radius = sigma / (2 * sqrt(r)) * (ppf(p_a) - ppf(p_b))
    # Corollary 1 is strict [eq. 12]; alg. 2 writes >=
    if radius > d:
        return top
    return ABSTAIN

# Smoothed Jacobian, first-order randomized estimator  [arxiv:2206.10787 §2.3]
# Input:  dynamics f, nominal point x_bar, noise std sigma, N samples
# Output: matrix J approximating the slope of the smoothed map

def smoothed_jacobian(f, x_bar, sigma, N):
    jacobians = []
    for _ in range(N):
        # Fresh Gaussian perturbation of the nominal point  [§2.1]
        w = normal(0, sigma**2, shape=dim_x)
        # Jacobian of the unsmoothed map at the sampled point  [§2.3]
        jacobians.append(jacobian(f, x_bar + w))
    # Average over samples  [§2.3]
    return mean(jacobians)

Contradictions

No direct disagreement between the two papers: they use the same averaging for different goals. Within papers:

• RAB's text says ImageNette certified accuracy is "around 12%" 2003.08904 §7.2.1. Its Table 1 gives 9.2-15.9% across the three patterns 2003.08904 tab. 1.
• RAB's text says ImageNette empirical accuracy is "over 30%" 2003.08904 §7.2.2. Its Table 1 gives 29.9% for the blending pattern, the lowest of the three 2003.08904 tab. 1.
• The contact paper's text says randomized smoothing runs about 2 to 3 times slower than analytic 2206.10787 §5.3. Its Table 2 shows about 4.4 times on PlanarHand (23.09 s vs 5.20 s) 2206.10787 tab. 2.

Papers

• RAB: Provable Robustness Against Backdoor Attacks: certifies predictions of a model trained on noised data against bounded backdoor triggers, for DNNs and exact KNN.
• Smoothing contact models for planning, by Pang et al.: smooths a convex contact model to get linearisations for iterative MPC and an RRT planner, with analytic and randomized estimators.