# Double Sampling Randomized Smoothing

arXiv: https://arxiv.org/abs/2206.07912 · HTML: https://mlsanity.com/paper/2206.07912/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 66 references that are in the map.
- First posted on arXiv 16 Jun 2022.

## Builds on (most cited first, 30 of 39)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [On Adaptive Attacks to Adversarial Example Defenses](https://mlsanity.com/paper/2002.08347/) (2020)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [Unlabeled Data Improves Adversarial Robustness](https://mlsanity.com/paper/1905.13736/) (2019)
- [Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers](https://mlsanity.com/paper/1906.04584/) (2019)
- [Certified Defenses against Adversarial Examples](https://mlsanity.com/paper/1801.09344/) (2018)
- [Adversarial GLUE: A Multi-Task Benchmark for Robustness Evaluation of Language Models](https://mlsanity.com/paper/2111.02840/) (2021)
- [Algorithms for Verifying Deep Neural Networks](https://mlsanity.com/paper/1903.06758/) (2019)
- [Towards Stable and Efficient Training of Verifiably Robust Neural Networks](https://mlsanity.com/paper/1906.06316/) (2019)
- [Certified Adversarial Robustness with Additive Noise](https://mlsanity.com/paper/1809.03113/) (2018)
- [Randomized Smoothing of All Shapes and Sizes](https://mlsanity.com/paper/2002.08118/) (2020)
- [MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radius](https://mlsanity.com/paper/2001.02378/) (2020)
- [QEBA: Query-Efficient Boundary-Based Blackbox Attack](https://mlsanity.com/paper/2005.14137/) (2020)
- [SemanticAdv: Generating Adversarial Examples via Attribute-conditional Image Editing](https://mlsanity.com/paper/1906.07927/) (2019)
- [Consistency Regularization for Certified Robustness of Smoothed Classifiers](https://mlsanity.com/paper/2006.04062/) (2020)
- [Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers](https://mlsanity.com/paper/1906.04948/) (2019)
- [Introduction to Neural Network Verification](https://mlsanity.com/paper/2109.10317/) (2021)
- [Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness](https://mlsanity.com/paper/2002.03239/) (2020)
- [TSS: Transformation-Specific Smoothing for Robustness Certification](https://mlsanity.com/paper/2002.12398/) (2020)
- [SmoothMix: Training Confidence-calibrated Smoothed Classifiers for Certified Robustness](https://mlsanity.com/paper/2111.09277/) (2021)
- [Detection as Regression: Certified Object Detection by Median Smoothing](https://mlsanity.com/paper/2007.03730/) (2020)
- [Black-Box Certification with Randomized Smoothing: A Functional Optimization Based Framework](https://mlsanity.com/paper/2002.09169/) (2020)
- [On the Certified Robustness for Ensemble Models and Beyond](https://mlsanity.com/paper/2107.10873/) (2021)
- [Improved, Deterministic Smoothing for L_1 Certified Robustness](https://mlsanity.com/paper/2103.10834/) (2021)

## Built on by (most cited first, 22 of 22)

- [LOT: Layer-wise Orthogonal Training on Improving ℓ2 Certified Robustness](https://mlsanity.com/paper/2210.11620/) (2022)
- [SafeAuto: Knowledge-Enhanced Safe Autonomous Driving with Multimodal Foundation Models](https://mlsanity.com/paper/2503.00211/) (2025)
- [Provably Unlearnable Data Examples](https://mlsanity.com/paper/2405.03316/) (2024)
- [Double Bubble, Toil and Trouble: Enhancing Certified Robustness through Transitivity](https://mlsanity.com/paper/2210.06077/) (2022)
- [Projected Randomized Smoothing for Certified Adversarial Robustness](https://mlsanity.com/paper/2309.13794/) (2023)
- [Multi-scale Diffusion Denoised Smoothing](https://mlsanity.com/paper/2310.16779/) (2023)
- [COLEP: Certifiably Robust Learning-Reasoning Conformal Prediction via Probabilistic Circuits](https://mlsanity.com/paper/2403.11348/) (2024)
- [Adaptive Randomized Smoothing: Certified Adversarial Robustness for Multi-Step Defences](https://mlsanity.com/paper/2406.10427/) (2024)
- [Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attacks](https://mlsanity.com/paper/2312.03979/) (2023)
- [Relational DNN Verification With Cross Executional Bound Refinement](https://mlsanity.com/paper/2405.10143/) (2024)
- [Rethinking Randomized Smoothing from the Perspective of Scalability](https://mlsanity.com/paper/2312.12608/) (2023)
- [COMMIT: Certifying Robustness of Multi-Sensor Fusion Systems against Semantic Attacks](https://mlsanity.com/paper/2403.02329/) (2024)
- [BEAVER: An Efficient Deterministic LLM Verifier](https://mlsanity.com/paper/2512.05439/) (2025)
- [Accelerated Smoothing: A Scalable Approach to Randomized Smoothing](https://mlsanity.com/paper/2402.07498/) (2024)
- [Effects of Exponential Gaussian Distribution on (Double Sampling) Randomized Smoothing](https://mlsanity.com/paper/2406.02309/) (2024)
- [Average Certified Radius is a Poor Metric for Randomized Smoothing](https://mlsanity.com/paper/2410.06895/) (2024)
- [CAMP in the Odyssey: Provably Robust Reinforcement Learning with Certified Radius Maximization](https://mlsanity.com/paper/2501.17667/) (2025)
- [Adversarial Examples in Environment Perception for Automated Driving (Review)](https://mlsanity.com/paper/2504.08414/) (2025)
- [[Re] Double Sampling Randomized Smoothing](https://mlsanity.com/paper/2306.15221/) (2023)
- [Dual Randomized Smoothing: Beyond Global Noise Variance](https://mlsanity.com/paper/2512.01782/) (2025)
- [Laplace-Bridged Randomized Smoothing for Fast Certified Robustness](https://mlsanity.com/paper/2604.24993/) (2026)
- [The Geometry of Randomized Smoothing on Feasible Sets](https://mlsanity.com/paper/2609.39497/) (2026)

## Abstract (arXiv)

Neural networks (NNs) are known to be vulnerable against adversarial perturbations, and thus there is a line of work aiming to provide robustness certification for NNs, such as randomized smoothing, which samples smoothing noises from a certain distribution to certify the robustness for a smoothed classifier. However, as shown by previous work, the certified robust radius in randomized smoothing suffers from scaling to large datasets ("curse of dimensionality"). To overcome this hurdle, we propose a Double Sampling Randomized Smoothing (DSRS) framework, which exploits the sampled probability from an additional smoothing distribution to tighten the robustness certification of the previous smoothed classifier. Theoretically, under mild assumptions, we prove that DSRS can certify Theta(√ d) robust radius under ℓ2 norm where d is the input dimension, implying that DSRS may be able to break the curse of dimensionality of randomized smoothing. We instantiate DSRS for a generalized family of Gaussian smoothing and propose an efficient and sound computing method based on customized dual optimization considering sampling error. Extensive experiments on MNIST, CIFAR-10, and ImageNet verify our theory and show that DSRS certifies larger robust radii than existing baselines consistently under different settings. Code is available at https://github.com/llylly/DSRS.