Dual Randomized Smoothing: Beyond Global Noise Variance

AI summary

Overview

Research area: Certified adversarial robustness of neural networks, specifically Randomized Smoothing (RS) for ℓ₂-norm perturbations, with extensions to input-dependent noise variances and mixture-of-experts routing.

Technical level: Advanced. The paper builds on the Lipschitz-continuity proof technique for RS certification and requires familiarity with Gaussian smoothing, certified radii, and confidence bounds.

Scope in one sentence: The paper proves that RS certification remains valid when noise variance is only locally constant, and uses this result to build a two-stage framework that predicts a per-input noise variance and then classifies with it, achieving strong certified accuracy at both small and large radii on CIFAR-10 and ImageNet.

Authors and venue: Chenhao Sun, Yuhao Mao, and Martin Vechev, Department of Computer Science, ETH Zürich, Switzerland. Posted as arXiv:2512.01782v4 [cs.LG], dated 15 Sep 2026 in the paper header (listed as published 2025-12-01). Code at https://github.com/eth-sri/Dual-Randomized-Smoothing. Licensed CC BY 4.0.

What This Paper Is About

Randomized Smoothing certifies a classifier by adding Gaussian noise to inputs and taking a majority vote, but it uses a single global noise variance for every input. Small variance gives high certified accuracy at small radii and large variance gives high accuracy at large radii, so no single global value performs well at both ends of the radius spectrum. The paper shows that the optimal variance actually varies substantially from sample to sample, and proposes a framework that lets a separate smoothed model choose the variance per input while still producing a valid certificate.

Key Contributions

1. Generalized certification to locally constant noise variance. The paper proves (Theorem 4.1) that the standard RS certificate stays valid when the variance σ(x) is input-dependent, as long as σ(x) is constant within the ball around each input, and extends this to a probabilistic version (Theorem 4.2) where the guarantee holds with probability at least 1 − α − β.

2. The Dual RS framework. A variance estimator g_e, itself smoothed with a global σ_e, predicts the optimal variance σ_c(x) for each input; a second RS classifier g_c is then smoothed with σ_c(x). The final certified radius is R_final = min(R_σ, R_c), where R_σ certifies the local constancy of the estimated variance and R_c certifies the classification.

3. Training procedures for both components. The paper builds a training set of optimal-σ labels by evaluating certified radii over a candidate set Σ, trains the variance estimator with soft labels (a softmax over certified radii) plus consistency regularization and class-balancing weights, and then finetunes the classifier under the estimated per-input variances in an alternating scheme.

4. A routing perspective with expert RS models. Because Theorem 4.2 does not require the same classifier h_c under every σ, the variance estimator can act as a router that selects among off-the-shelf expert RS models, each specializing in one noise level.

5. Extensive evaluation. Dual RS is tested on CIFAR-10 and ImageNet, with large gains over prior input-dependent RS and roughly 60% inference overhead relative to standard RS.

Main Findings

• The optimal variance is sample-dependent. Figure 1 shows the distribution of the optimal σ on the CIFAR-10 test set (with the base model fixed to the pretrained denoised smoothing model of Carlini et al., 2023) and the certified radius curves of five independent samples against σ, illustrating that no single global σ is optimal across inputs.

• No global variance works across radii. On CIFAR-10, the pretrained diffusion denoised smoothing model with σ = 0.25 gets 86.61% certified accuracy at radius 0.00 and 35.30% at radius 0.75 but 0.00% at radius 1.00 and beyond; σ = 0.5 reaches 49.46% at radius 0.50 and 28.58% at 1.00, then 0.00% from 1.75; σ = 1.0 is weak at small radii (47.98% at 0.00, 19.34% at 1.00) but retains 2.15% at radius 2.50.

• Dual RS with a single pretrained classifier is strong across all radii. Using the same classifier, Dual RS over Σ = {0.25, 0.5, 1.0} reaches 68.34% at radius 0.00, 41.28% at 0.50, 29.01% at 0.75, 19.85% at 1.00, 12.73% at 1.25, 7.62% at 1.50, 4.73% at 1.75, 3.54% at 2.00, 2.62% at 2.25, and 1.83% at 2.50.

• Dual RS beats the state-of-the-art input-dependent method at most radii. Against Multiscale (Jeong & Shin, 2024) with finetuning, Dual RS reaches 70.53%, 57.48%, 45.27%, 34.15%, 24.68%, 17.84%, 12.46%, 8.83%, 6.65%, 4.73%, and 3.14% at radii 0.00 through 2.50, versus Multiscale's 76.51%, 54.78%, 39.15%, 28.46%, 21.33%, 15.95%, 11.40%, 7.91%, 5.31%, 3.63%, and 2.34%. Multiscale is higher only at radius 0.00 in this comparison.

• Relative improvements at key radii. Dual RS improves certified accuracy by 15.6%, 20.0%, and 15.7% at radii 0.5, 0.75, and 1.0 on CIFAR-10, and delivers 8.6%, 17.1%, and 9.1% performance advantages at radii 0.5, 1.0, and 1.5 on ImageNet.

• Modest inference overhead. On a single NVIDIA RTX 4090 GPU with batch size 1000 and N = 10,000, certifying with Dual RS takes 22.58 seconds per input on average, versus 14.07 seconds for standard RS and 20.21 seconds for Multiscale — roughly 60% overhead over standard RS. Multiscale's time grows with rounds (14.07, 28.14, and 42.21 seconds on average for 1, 2, and 3 rounds), while Dual RS spends a fixed amount of time for all inputs.

• ImageNet results. Off-the-shelf denoised smoothing on ImageNet with σ = 0.5 gives 74.4%, 64.4%, 52.4%, 34.8%, and 0.0% at radii 0.0, 0.5, 1.0, 1.5, and 2.0; with σ = 1.0 it gives 56.0%, 47.8%, 37.4%, 29.4%, and 24.0%. The ImageNet table of Dual RS numbers is cut off in the provided content, so its per-radius entries are not reported here; the abstract-level gains of 8.6%, 17.1%, and 9.1% at radii 0.5, 1.0, and 1.5 stand as the reported comparison.

• The confidence penalty from the second certification is small. Theorem 4.2 costs a β term in the failure probability; the authors report numerical examples under different configurations in Table 5 (App. D) showing β has minimal impact on the certified radius.

• One round of alternating training suffices. Training the variance estimator from scratch on top of the off-the-shelf classifier plus one round of classifier finetuning is usually sufficient; more rounds yield marginal improvements at much higher computational cost (App. E.2).

• Training-time efficiency tricks work. Using a smaller budget N = 100 to estimate R_c(x, σ_i) matches the cost of a single RS inference with minimal performance degradation (App. E.4), and inputs with zero certified radius across all σ_i are discarded.

Methodology in Plain English

The approach starts from a proof technique rather than a new architecture. The authors take the existing RS certificate and show that it survives if the noise level is held constant only within the neighborhood being certified — the variance can vary arbitrarily outside that neighborhood. This matters because it removes the global-constant assumption that forced the trade-off, and it means the variance function can be learned rather than memorized at test time.

Because a learned variance function cannot be assumed constant, the authors certify its constancy with a second randomized smoothing model. The first model, the variance estimator, is smoothed with a global σ_e chosen to be at least as large as the largest candidate variance in Σ, so it never limits the final radius. It predicts which σ from a discrete set Σ is best for the input. The second model then performs ordinary RS classification at that predicted σ. The final certificate is the smaller of the two certified radii, and the two failure probabilities add up by a union bound.

Training happens in stages. First, for each training input, the authors run certification under every candidate σ and record the resulting radius; the σ with the largest radius becomes the target. They then train the variance estimator on soft labels — a softmax distribution over the certified radii — so that predicting a near-optimal σ is penalized less than predicting a wildly wrong one. They add consistency regularization from Jeong & Shin (2020), reweight the classes by 1/q_i because the optimal-σ distribution is skewed, and scale the regularization weight by either a weak (R_c at the minimum predicted σ) or a strong (R_c at the maximum predicted σ) schedule; the strong version works slightly better on CIFAR-10 and the weak version on ImageNet. Finally, they finetune the classifier under the estimated per-input variances using the same procedure as Carlini et al. (2023), differing only in that the noise level is now input-dependent.

The routing variant reuses the same variance estimator but swaps in whichever pretrained expert classifier performs best at the selected σ, so the estimator doubles as a router. Because certification under Dual RS is cheap once expert radii are known, new experts can be added by retraining only the lightweight estimator.

Why This Matters

Impact on research. The paper weakens a core assumption of randomized smoothing — that the smoothing distribution must be globally fixed — and shows certification still holds under local constancy. This unlocks a large design space: any learned or hand-crafted variance function, provided its local constancy is certified. It also reframes RS as a routing problem, which the authors note can be extended to deterministic certification methods, not just RS. Compared with prior input-dependent work (Wang et al., 2021; Alfarra et al., 2022; Súkeník et al., 2022; Jeong & Shin, 2024), Table 1 positions Dual RS as the first entry with flexible σ, no test-time memorization, flexible routing, and certified routing simultaneously.

Real-world applications.

• Safety-critical perception systems (for example, autonomous driving or robotics) where a single model must be trustworthy both for small perturbations near the input and for larger adversarial shifts.
• Medical imaging pipelines, where certified predictions must hold across a range of perturbation magnitudes arising from acquisition variability.
• Malware and content classification, where attackers adapt perturbation size and a fixed noise budget is easy to game.
• Deployment of heterogeneous certification models, where the routing view lets existing expert models be combined without retraining a monolithic classifier.

Industry relevance. The framework's practical selling points are its use of off-the-shelf diffusion denoisers and pretrained classifiers, a training pass that can be parallelized across devices and only done once, and a fixed per-input inference cost (22.58 seconds per input at batch size 1000 on an RTX 4090) rather than a cost that grows with certification rounds as in Multiscale. The routing formulation also lowers the barrier to incremental improvement: adding a better expert requires retraining only the lightweight variance estimator.

Future Directions

• Extending routing beyond RS to deterministic certification. The authors explicitly suggest that a pool of experts trained with different algorithms and hyperparameters could be combined by an RS router, with the final radius being the minimum of the routing model's radius and the selected expert's radius, and leave this to future work.

• More alternating training rounds. The paper reports that one round of classifier finetuning is usually sufficient, and that additional rounds may bring marginal gains at much higher cost — a cost/benefit question left open.

• Broader candidate sets and norms. The experiments use Σ = {0.25, 0.5, 1.0} on CIFAR-10 and {0.5, 1.0} on ImageNet, and the authors note prior ℓ∞ work (Lyu et al., 2024) does not generalize to ℓ₂; scaling Σ and extending the framework to other norms is unexplored.

• Scaling to harder datasets and models. The ImageNet results rely on a 552M-parameter diffusion denoiser and a 305M-parameter BEiT classifier; whether the training pipeline scales to larger expert pools and harder tasks remains an open question, and the reported ImageNet certification numbers in Table 3 are partially truncated in the available content.

Target Audience

Researchers and practitioners in adversarial machine learning and certified robustness who already understand randomized smoothing and want to push past the global-variance trade-off. It is most useful to those building deployable certified classifiers — particularly anyone using diffusion-based denoised smoothing (Carlini et al., 2023) or multi-scale certification (Jeong & Shin, 2024) — and to readers interested in routing and mixture-of-experts as a mechanism for certified rather than merely empirical robustness. Students with a background in the Cohen et al. (2019) RS framework will get the most from the theory sections, while engineers will find the training recipes, weighting schemes, and timing results directly actionable.

Authors’ abstract

Randomized Smoothing (RS) is a prominent technique for certifying the robustness of neural networks against adversarial perturbations. With RS, achieving high accuracy at small radii requires a small noise variance, while achieving high accuracy at large radii requires a large noise variance. However, the global noise variance used in the standard RS formulation leads to a fundamental limitation: there exists no global noise variance that simultaneously achieves strong performance at both small and large radii. To break through the global variance limitation, we propose a dual RS framework which enables input-dependent noise variances. To achieve that, we first prove that RS remains valid with input-dependent noise variances, provided the variance is locally constant around each input. Building on this result, we introduce two components: (i) a variance estimator predicts an optimal noise variance for each input, (ii) this estimated variance is then used by a standard RS classifier. The variance estimator is independently smoothed via RS to ensure local constancy, enabling flexible design. We also introduce training strategies to iteratively optimize the two components. Experiments on CIFAR-10 demonstrate that our dual RS method provides strong performance for both small and large radii-unattainable with global noise variance-while incurring only a 60% computational overhead at inference. Moreover, it outperforms prior input-dependent noise approaches across most radii, with gains at radii 0.5, 0.75, and 1.0 of 15.6%, 20.0%, and 15.7%. On ImageNet, dual RS remains effective across all radii, with advantages of 8.6%, 17.1%, and 9.1% at radii 0.5, 1.0, and 1.5. Additionally, the dual RS framework provides a routing perspective for certified robustness, improving the accuracy-robustness trade-off with off-the-shelf expert RS models.