--- kind: concept slug: randomized-smoothing title: Randomized smoothing summary: >- Randomized smoothing averages a function over random noise. Used as a classifier, it gives certified predictions against bounded training-set or test-time perturbations, at low author-reported accuracy on image tasks. Used on a contact model, it gives usable slopes for planning, with no certificate. Numbers are author-reported. tags: [robustness, certification, sampling, robotics] papers: ["2003.08904", "2206.10787"] related: [adversarial-robustness, backdoor-attack, data-poisoning, trajectory-optimization, differentiable-simulation, heavy-tailed-noise] status: draft updated_at: 2026-11-08 --- ## 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 [arxiv:2003.08904 §1] [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv:2206.10787 §2.1] [arxiv: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 [arxiv: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) $$ [arxiv: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](/papers/2003.08904). 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 [arxiv:2003.08904 tab. 1] [arxiv:2003.08904 §7.1.5]. Benign accuracy on CIFAR-10 falls by about 2.6 to 3.7 points against the vanilla model [arxiv:2003.08904 tab. 1]. Abstention rates are 1.9-6.0% [arxiv: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 [arxiv:2003.08904 §7.1.2]. Certifying one input takes N forward passes [arxiv:2003.08904 §9]. - The radius shrinks with the square root of the poisoned count [arxiv:2003.08904 §5.1.2]. The table numbers do not say which r was used [arxiv: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 [arxiv: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 [arxiv:2003.08904 §6.2] [thm. 3]. The cost is O(K^(2+C) · n² · L · C) for C classes and n training points [arxiv:2003.08904 app. B]. Reported certified accuracy on Spambase with K=3 and σ=0.5 is 33.3-41.7% [arxiv:2003.08904 tab. 2], and certifying one input takes 2.5 s [arxiv:2003.08904 §7.3]. The paper's linear-time claim for K=1 is not derived in its appendix [arxiv: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¹ [arxiv:2206.10787 §2.1]. Three estimators give the local linear model used by the planner [arxiv:2206.10787 §2.2] [arxiv: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 [arxiv:2206.10787 §4.2] [arxiv:2206.10787 §5.1]. For a 1-D frictionless cart it equals randomized smoothing with a heavy-tailed elliptical density [arxiv:2206.10787 §4.3]. The authors report similar results on frictional examples, without a proof [arxiv:2206.10787 fig. 5]. - **First-order randomized.** Average the Jacobians of f at sampled points. This needs f to be locally Lipschitz [arxiv: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 [arxiv:2206.10787 §2.3]. Minimum iMPC cost over iterations, author-reported [arxiv:2206.10787 tab. 2]: | Method | PlanarPushing | PlanarHand | AllegroHand | |---|---|---|---| | Analytic | 11.74 | 26.55 | 5.78 | | Randomized first-order | 11.73 | 17.87 | 8.42 | | Randomized zero-order | 12.86 | 18.29 | 28.21 | | Exact (no smoothing) | 31.64 | 18.49 | 44.68 | On the RRT planner, the analytic variant ran faster than both randomized variants on all six tasks [arxiv:2206.10787 tab. 3]. The zero-order RRT row cannot be reproduced from the released code, and the paper reports no success rates [arxiv:2206.10787 §8.1]. Card: [Smoothing contact models for planning](/papers/2206.10787). ## When to use which | Situation | Use | Why | |---|---|---| | Classifier is a DNN, a provable bound on backdoor triggers is needed, and N full trainings are affordable | Training-set smoothing (DNN) | Gives a radius certificate against training-time triggers [arxiv:2003.08904 §5.1.2]; cost is N models [arxiv:2003.08904 §7.1.2] | | Classifier is KNN on squared Euclidean distance, quantised into levels | Exact KNN smoothing | No sampling needed [arxiv:2003.08904 §6.2]; K>1 numbers are not reproducible from the released code | | Certificate only at test time, against evasion | Test-time smoothing (training noise set to zero) | This is the special case of the RAB framework [arxiv:2003.08904 §4.1.1] | | Need slopes of a contact model, and the analytic form (or a barrier) is available | Analytic smoothing | One solve per linearisation, where randomized uses N = 100 [arxiv:2206.10787 §5.3]; lowest cost on AllegroHand [arxiv:2206.10787 tab. 2] | | Need slopes, and only Jacobians of a locally Lipschitz map are available | First-order randomized | Needs Lipschitz f [arxiv:2206.10787 §2.3]; the Jacobian of a step is zero almost everywhere [arxiv:2206.10787 §2.3] | | Need slopes through discontinuities, and only function values are available | Zero-order randomized | Works for discontinuous f [arxiv:2206.10787 §2.3]; noisier, as on AllegroHand [arxiv:2206.10787 tab. 2] | 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 [arxiv: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 [arxiv:2206.10787 §5.2] [arxiv: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. ```pseudocode # 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 ``` ```pseudocode # 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%" [arxiv:2003.08904 §7.2.1]. Its Table 1 gives 9.2-15.9% across the three patterns [arxiv:2003.08904 tab. 1]. - RAB's text says ImageNette empirical accuracy is "over 30%" [arxiv:2003.08904 §7.2.2]. Its Table 1 gives 29.9% for the blending pattern, the lowest of the three [arxiv:2003.08904 tab. 1]. - The contact paper's text says randomized smoothing runs about 2 to 3 times slower than analytic [arxiv:2206.10787 §5.3]. Its Table 2 shows about 4.4 times on PlanarHand (23.09 s vs 5.20 s) [arxiv:2206.10787 tab. 2]. ## Papers - [RAB: Provable Robustness Against Backdoor Attacks](/papers/2003.08904): certifies predictions of a model trained on noised data against bounded backdoor triggers, for DNNs and exact KNN. - [Smoothing contact models for planning](/papers/2206.10787), by Pang et al.: smooths a convex contact model to get linearisations for iterative MPC and an RRT planner, with analytic and randomized estimators.