# Mitigating the Curse of Dimensionality for Certified Robustness via Dual Randomized Smoothing

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 49 references that are in the map.
- First posted on arXiv 15 Apr 2024.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Improved Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2102.09672/) (2021)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Natural Adversarial Examples](https://mlsanity.com/paper/1907.07174/) (2019)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Adversarial Training for Free!](https://mlsanity.com/paper/1904.12843/) (2019)
- [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)
- [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)
- [MOSE: A New Dataset for Video Object Segmentation in Complex Scenes](https://mlsanity.com/paper/2302.01872/) (2023)
- [MeViS: A Large-scale Benchmark for Video Segmentation with Motion Expressions](https://mlsanity.com/paper/2308.08544/) (2023)
- [MMA Training: Direct Input Space Margin Maximization through Adversarial Training](https://mlsanity.com/paper/1812.02637/) (2018)
- [Towards Open Vocabulary Learning: A Survey](https://mlsanity.com/paper/2306.15880/) (2023)
- [Efficient Formal Safety Analysis of Neural Networks](https://mlsanity.com/paper/1809.08098/) (2018)
- [Randomized Smoothing of All Shapes and Sizes](https://mlsanity.com/paper/2002.08118/) (2020)
- [(Certified!!) Adversarial Robustness for Free!](https://mlsanity.com/paper/2206.10550/) (2022)
- [An approach to reachability analysis for feed-forward ReLU neural networks](https://mlsanity.com/paper/1706.07351/) (2017)
- [MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radius](https://mlsanity.com/paper/2001.02378/) (2020)
- [VLT: Vision-Language Transformer and Query Generation for Referring Segmentation](https://mlsanity.com/paper/2210.15871/) (2022)
- [Consistency Regularization for Certified Robustness of Smoothed Classifiers](https://mlsanity.com/paper/2006.04062/) (2020)
- [Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness](https://mlsanity.com/paper/2002.03239/) (2020)
- [AdvDrop: Adversarial Attack to DNNs by Dropping Information](https://mlsanity.com/paper/2108.09034/) (2021)
- [Meta Gradient Adversarial Attack](https://mlsanity.com/paper/2108.04204/) (2021)
- [Beyond the Prior Forgery Knowledge: Mining Critical Clues for General Face Forgery Detection](https://mlsanity.com/paper/2304.12489/) (2023)

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

- [Transferable Adversarial Attacks on SAM and Its Downstream Models](https://mlsanity.com/paper/2410.20197/) (2024)
- [Purify Unlearnable Examples via Rate-Constrained Variational Autoencoders](https://mlsanity.com/paper/2405.01460/) (2024)
- [Semantic Deep Hiding for Robust Unlearnable Examples](https://mlsanity.com/paper/2406.17349/) (2024)
- [When Robots Obey the Patch: Universal Transferable Patch Attacks on Vision-Language-Action Models](https://mlsanity.com/paper/2511.21192/) (2025)
- [Backdoor Attacks against No-Reference Image Quality Assessment Models via a Scalable Trigger](https://mlsanity.com/paper/2412.07277/) (2024)
- [MTL-UE: Learning to Learn Nothing for Multi-Task Learning](https://mlsanity.com/paper/2505.05279/) (2025)
- [Towards Model Resistant to Transferable Adversarial Examples via Trigger Activation](https://mlsanity.com/paper/2504.14541/) (2025)
- [Unlearnable Examples Detection via Iterative Filtering](https://mlsanity.com/paper/2408.08143/) (2024)
- [Towards Physical World Backdoor Attacks against Skeleton Action Recognition](https://mlsanity.com/paper/2408.08671/) (2024)
- [Time Is All It Takes: Spike-Retiming Attacks on Event-Driven Spiking Neural Networks](https://mlsanity.com/paper/2602.03284/) (2026)
- [AEGIS: Adversarial Target-Guided Retention-Data-Free Robust Concept Erasure from Diffusion Models](https://mlsanity.com/paper/2602.06771/) (2026)
- [Certified vs. Empirical Adversarial Robust-ness via Hybrid Convolutions with Attention Stochasticity](https://mlsanity.com/paper/2605.01519/) (2026)
- [Dual Randomized Smoothing: Beyond Global Noise Variance](https://mlsanity.com/paper/2512.01782/) (2025)
- [Feature-Space Smoothing: Certified Robustness of Deep Representations](https://mlsanity.com/paper/2601.16200/) (2026)
- [Covert Visual Prompt Injection against Commercial Multimodal Large Language Models](https://mlsanity.com/paper/2603.29418/) (2026)

## Abstract (arXiv)

Randomized Smoothing (RS) has been proven a promising method for endowing an arbitrary image classifier with certified robustness. However, the substantial uncertainty inherent in the high-dimensional isotropic Gaussian noise imposes the curse of dimensionality on RS. Specifically, the upper bound of ℓ2 certified robustness radius provided by RS exhibits a diminishing trend with the expansion of the input dimension d, proportionally decreasing at a rate of 1/√d. This paper explores the feasibility of providing ℓ2 certified robustness for high-dimensional input through the utilization of dual smoothing in the lower-dimensional space. The proposed Dual Randomized Smoothing (DRS) down-samples the input image into two sub-images and smooths the two sub-images in lower dimensions. Theoretically, we prove that DRS guarantees a tight ℓ2 certified robustness radius for the original input and reveal that DRS attains a superior upper bound on the ℓ2 robustness radius, which decreases proportionally at a rate of (1/√ m + 1/√ n ) with m+n=d. Extensive experiments demonstrate the generalizability and effectiveness of DRS, which exhibits a notable capability to integrate with established methodologies, yielding substantial improvements in both accuracy and ℓ2 certified robustness baselines of RS on the CIFAR-10 and ImageNet datasets. Code is available at https://github.com/xiasong0501/DRS.