# Improved, Deterministic Smoothing for L_1 Certified Robustness

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 39 references that are in the map.
- First posted on arXiv 17 Mar 2021.

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

- [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)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers](https://mlsanity.com/paper/1906.04584/) (2019)
- [On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models](https://mlsanity.com/paper/1810.12715/) (2018)
- [Sorting out Lipschitz function approximation](https://mlsanity.com/paper/1811.05381/) (2018)
- [Certified Adversarial Robustness with Additive Noise](https://mlsanity.com/paper/1809.03113/) (2018)
- [Semidefinite relaxations for certifying robustness to adversarial examples](https://mlsanity.com/paper/1811.01057/) (2018)
- [EAD: Elastic-Net Attacks to Deep Neural Networks via Adversarial Examples](https://mlsanity.com/paper/1709.04114/) (2017)
- [Randomized Smoothing of All Shapes and Sizes](https://mlsanity.com/paper/2002.08118/) (2020)
- [RAB: Provable Robustness Against Backdoor Attacks](https://mlsanity.com/paper/2003.08904/) (2020)
- [Deep Partition Aggregation: Provable Defense against General Poisoning Attacks](https://mlsanity.com/paper/2006.14768/) (2020)
- [MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radius](https://mlsanity.com/paper/2001.02378/) (2020)
- [Certified Robustness to Label-Flipping Attacks via Randomized Smoothing](https://mlsanity.com/paper/2002.03018/) (2020)
- [SoK: Certified Robustness for Deep Neural Networks](https://mlsanity.com/paper/2009.04131/) (2020)
- [Certified Defenses for Adversarial Patches](https://mlsanity.com/paper/2003.06693/) (2020)
- [(De)Randomized Smoothing for Certifiable Defense against Patch Attacks](https://mlsanity.com/paper/2002.10733/) (2020)
- [Preventing Gradient Attenuation in Lipschitz Constrained Convolutional Networks](https://mlsanity.com/paper/1911.00937/) (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)
- [Robustness Certificates for Sparse Adversarial Attacks by Randomized Ablation](https://mlsanity.com/paper/1911.09272/) (2019)
- [Certified Defense to Image Transformations via Randomized Smoothing](https://mlsanity.com/paper/2002.12463/) (2020)
- [Second-Order Provable Defenses against Adversarial Attacks](https://mlsanity.com/paper/2006.00731/) (2020)
- [Higher-Order Certification for Randomized Smoothing](https://mlsanity.com/paper/2010.06651/) (2020)
- [Certifiably Robust Interpretation in Deep Learning](https://mlsanity.com/paper/1905.12105/) (2019)
- [Wasserstein Smoothing: Certified Robustness against Wasserstein Adversarial Attacks](https://mlsanity.com/paper/1910.10783/) (2019)

## Built on by (most cited first, 30 of 39)

- [Improved deterministic l2 robustness on CIFAR-10 and CIFAR-100](https://mlsanity.com/paper/2108.04062/) (2021)
- [Policy Smoothing for Provably Robust Reinforcement Learning](https://mlsanity.com/paper/2106.11420/) (2021)
- [On the Certified Robustness for Ensemble Models and Beyond](https://mlsanity.com/paper/2107.10873/) (2021)
- [ANCER: Anisotropic Certification via Sample-wise Volume Maximization](https://mlsanity.com/paper/2107.04570/) (2021)
- [Double Sampling Randomized Smoothing](https://mlsanity.com/paper/2206.07912/) (2022)
- [Explicit Tradeoffs between Adversarial and Natural Distributional Robustness](https://mlsanity.com/paper/2209.07592/) (2022)
- [Mutual Adversarial Training: Learning together is better than going alone](https://mlsanity.com/paper/2112.05005/) (2021)
- [Robust Yet Efficient Conformal Prediction Sets](https://mlsanity.com/paper/2407.09165/) (2024)
- [Stability Guarantees for Feature Attributions with Multiplicative Smoothing](https://mlsanity.com/paper/2307.05902/) (2023)
- [Projected Randomized Smoothing for Certified Adversarial Robustness](https://mlsanity.com/paper/2309.13794/) (2023)
- [Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networks](https://mlsanity.com/paper/2301.02039/) (2023)
- [A.I. Robustness: a Human-Centered Perspective on Technological Challenges and Opportunities](https://mlsanity.com/paper/2210.08906/) (2022)
- [Hierarchical Randomized Smoothing](https://mlsanity.com/paper/2310.16221/) (2023)
- [Multi-scale Diffusion Denoised Smoothing](https://mlsanity.com/paper/2310.16779/) (2023)
- [Probabilistic Stability Guarantees for Feature Attributions](https://mlsanity.com/paper/2504.13787/) (2025)
- [Asymmetric Certified Robustness via Feature-Convex Neural Networks](https://mlsanity.com/paper/2302.01961/) (2023)
- [Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attacks](https://mlsanity.com/paper/2312.03979/) (2023)
- [Treatment of Statistical Estimation Problems in Randomized Smoothing for Adversarial Robustness](https://mlsanity.com/paper/2406.17830/) (2024)
- [Invariance-Aware Randomized Smoothing Certificates](https://mlsanity.com/paper/2211.14207/) (2022)
- [Towards the Worst-case Robustness of Large Language Models](https://mlsanity.com/paper/2501.19040/) (2025)
- [Certifying Model Accuracy under Distribution Shifts](https://mlsanity.com/paper/2201.12440/) (2022)
- [(De-)Randomized Smoothing for Decision Stump Ensembles](https://mlsanity.com/paper/2205.13909/) (2022)
- [Adversarial Feature Alignment: Balancing Robustness and Accuracy in Deep Learning via Adversarial Training](https://mlsanity.com/paper/2402.12187/) (2024)
- [Fast Certification of Vision-Language Models Using Incremental Randomized Smoothing](https://mlsanity.com/paper/2311.09024/) (2023)
- [Robust Conformal Prediction with a Single Binary Certificate](https://mlsanity.com/paper/2503.05239/) (2025)
- [Sound Randomized Smoothing in Floating-Point Arithmetics](https://mlsanity.com/paper/2207.07209/) (2022)
- [Exploring Geometry of Blind Spots in Vision Models](https://mlsanity.com/paper/2310.19889/) (2023)
- [AuditVotes: Elevating Provable Defense for GNNs with Efficient Augmentation and Conditional Smoothing](https://mlsanity.com/paper/2503.22998/) (2025)
- [Smooth-Reduce: Leveraging Patches for Improved Certified Robustness](https://mlsanity.com/paper/2205.06154/) (2022)
- [Towards Large Certified Radius in Randomized Smoothing using Quasiconcave Optimization](https://mlsanity.com/paper/2302.00209/) (2023)

## Abstract (arXiv)

Randomized smoothing is a general technique for computing sample-dependent robustness guarantees against adversarial attacks for deep classifiers. Prior works on randomized smoothing against L_1 adversarial attacks use additive smoothing noise and provide probabilistic robustness guarantees. In this work, we propose a non-additive and deterministic smoothing method, Deterministic Smoothing with Splitting Noise (DSSN). To develop DSSN, we first develop SSN, a randomized method which involves generating each noisy smoothing sample by first randomly splitting the input space and then returning a representation of the center of the subdivision occupied by the input sample. In contrast to uniform additive smoothing, the SSN certification does not require the random noise components used to be independent. Thus, smoothing can be done effectively in just one dimension and can therefore be efficiently derandomized for quantized data (e.g., images). To the best of our knowledge, this is the first work to provide deterministic "randomized smoothing" for a norm-based adversarial threat model while allowing for an arbitrary classifier (i.e., a deep model) to be used as a base classifier and without requiring an exponential number of smoothing samples. On CIFAR-10 and ImageNet datasets, we provide substantially larger L_1 robustness certificates compared to prior works, establishing a new state-of-the-art. The determinism of our method also leads to significantly faster certificate computation. Code is available at: https://github.com/alevine0/smoothingSplittingNoise