# Intriguing Properties of Input-dependent Randomized Smoothing

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 41 references that are in the map.
- First posted on arXiv 11 Oct 2021.

## Builds on (most cited first, 29 of 29)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [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)
- [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)
- [Adversarial Machine Learning at Scale](https://mlsanity.com/paper/1611.01236/) (2016)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Adversarial Examples Are Not Easily Detected: Bypassing Ten Detection Methods](https://mlsanity.com/paper/1705.07263/) (2017)
- [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)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Sorting out Lipschitz function approximation](https://mlsanity.com/paper/1811.05381/) (2018)
- [Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks](https://mlsanity.com/paper/1802.04034/) (2018)
- [Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulation](https://mlsanity.com/paper/1705.08475/) (2017)
- [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)
- [Deep Learning Through the Lens of Example Difficulty](https://mlsanity.com/paper/2106.09647/) (2021)
- [Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness](https://mlsanity.com/paper/2002.03239/) (2020)
- [On the Robustness of the CVPR 2018 White-Box Adversarial Example Defenses](https://mlsanity.com/paper/1804.03286/) (2018)
- [Higher-Order Certification for Randomized Smoothing](https://mlsanity.com/paper/2010.06651/) (2020)
- [Data-Dependent Randomized Smoothing](https://mlsanity.com/paper/2012.04351/) (2020)
- [Expressivity of Deep Neural Networks](https://mlsanity.com/paper/2007.04759/) (2020)
- [ANCER: Anisotropic Certification via Sample-wise Volume Maximization](https://mlsanity.com/paper/2107.04570/) (2021)
- [Extensions and limitations of randomized smoothing for robustness guarantees](https://mlsanity.com/paper/2006.04208/) (2020)
- [Hidden Cost of Randomized Smoothing](https://mlsanity.com/paper/2003.01249/) (2020)
- [Insta-RS: Instance-wise Randomized Smoothing for Improved Robustness and Accuracy](https://mlsanity.com/paper/2103.04436/) (2021)
- [Analyzing Accuracy Loss in Randomized Smoothing Defenses](https://mlsanity.com/paper/2003.01595/) (2020)

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

- [Double Sampling Randomized Smoothing](https://mlsanity.com/paper/2206.07912/) (2022)
- [Provably Unlearnable Data Examples](https://mlsanity.com/paper/2405.03316/) (2024)
- [Mitigating the Curse of Dimensionality for Certified Robustness via Dual Randomized Smoothing](https://mlsanity.com/paper/2404.09586/) (2024)
- [Robust and Accurate -- Compositional Architectures for Randomized Smoothing](https://mlsanity.com/paper/2204.00487/) (2022)
- [Projected Randomized Smoothing for Certified Adversarial Robustness](https://mlsanity.com/paper/2309.13794/) (2023)
- [Hierarchical Randomized Smoothing](https://mlsanity.com/paper/2310.16221/) (2023)
- [Multi-scale Diffusion Denoised Smoothing](https://mlsanity.com/paper/2310.16779/) (2023)
- [Adaptive Randomized Smoothing: Certified Adversarial Robustness for Multi-Step Defences](https://mlsanity.com/paper/2406.10427/) (2024)
- [Understanding Noise-Augmented Training for Randomized Smoothing](https://mlsanity.com/paper/2305.04746/) (2023)
- [Rethinking Randomized Smoothing from the Perspective of Scalability](https://mlsanity.com/paper/2312.12608/) (2023)
- [Smooth-Reduce: Leveraging Patches for Improved Certified Robustness](https://mlsanity.com/paper/2205.06154/) (2022)
- [An Overview and Prospective Outlook on Robust Training and Certification of Machine Learning Models](https://mlsanity.com/paper/2208.07464/) (2022)
- [Towards Large Certified Radius in Randomized Smoothing using Quasiconcave Optimization](https://mlsanity.com/paper/2302.00209/) (2023)
- [Robust width: A lightweight and certifiable adversarial defense](https://mlsanity.com/paper/2405.15971/) (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)
- [Towards Strong Certified Defense with Universal Asymmetric Randomization](https://mlsanity.com/paper/2510.19977/) (2025)
- [Certified vs. Empirical Adversarial Robust-ness via Hybrid Convolutions with Attention Stochasticity](https://mlsanity.com/paper/2605.01519/) (2026)
- [Variational Randomized Smoothing for Sample-Wise Adversarial Robustness](https://mlsanity.com/paper/2407.11844/) (2024)
- [AdaptDel: Adaptable Deletion Rate Randomized Smoothing for Certified Robustness](https://mlsanity.com/paper/2511.09316/) (2025)
- [Dual Randomized Smoothing: Beyond Global Noise Variance](https://mlsanity.com/paper/2512.01782/) (2025)
- [Clustered Randomized Smoothing for Stochastic Prediction Functions](https://mlsanity.com/paper/2608.12037/) (2026)
- [The Geometry of Randomized Smoothing on Feasible Sets](https://mlsanity.com/paper/2609.39497/) (2026)

## Abstract (arXiv)

Randomized smoothing is currently considered the state-of-the-art method to obtain certifiably robust classifiers. Despite its remarkable performance, the method is associated with various serious problems such as "certified accuracy waterfalls", certification vs. accuracy trade-off, or even fairness issues. Input-dependent smoothing approaches have been proposed with intention of overcoming these flaws. However, we demonstrate that these methods lack formal guarantees and so the resulting certificates are not justified. We show that in general, the input-dependent smoothing suffers from the curse of dimensionality, forcing the variance function to have low semi-elasticity. On the other hand, we provide a theoretical and practical framework that enables the usage of input-dependent smoothing even in the presence of the curse of dimensionality, under strict restrictions. We present one concrete design of the smoothing variance function and test it on CIFAR10 and MNIST. Our design mitigates some of the problems of classical smoothing and is formally underlined, yet further improvement of the design is still necessary.