# Higher-Order Certification for Randomized Smoothing

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Oct 2020.

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

- [SmoothMix: Training Confidence-calibrated Smoothed Classifiers for Certified Robustness](https://mlsanity.com/paper/2111.09277/) (2021)
- [Boosting Randomized Smoothing with Variance Reduced Classifiers](https://mlsanity.com/paper/2106.06946/) (2021)
- [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)
- [Scalable Certified Segmentation via Randomized Smoothing](https://mlsanity.com/paper/2107.00228/) (2021)
- [Intriguing Properties of Input-dependent Randomized Smoothing](https://mlsanity.com/paper/2110.05365/) (2021)
- [ANCER: Anisotropic Certification via Sample-wise Volume Maximization](https://mlsanity.com/paper/2107.04570/) (2021)
- [CC-Cert: A Probabilistic Approach to Certify General Robustness of Neural Networks](https://mlsanity.com/paper/2109.10696/) (2021)
- [Certified Adversarial Defenses Meet Out-of-Distribution Corruptions: Benchmarking Robustness and Simple Baselines](https://mlsanity.com/paper/2112.00659/) (2021)
- [NLP Verification: Towards a General Methodology for Certifying Robustness](https://mlsanity.com/paper/2403.10144/) (2024)
- [Double Bubble, Toil and Trouble: Enhancing Certified Robustness through Transitivity](https://mlsanity.com/paper/2210.06077/) (2022)
- [Incremental Randomized Smoothing Certification](https://mlsanity.com/paper/2305.19521/) (2023)
- [Holistic Adversarial Robustness of Deep Learning Models](https://mlsanity.com/paper/2202.07201/) (2022)
- [Input-agnostic Certified Group Fairness via Gaussian Parameter Smoothing](https://mlsanity.com/paper/2206.11423/) (2022)
- [Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networks](https://mlsanity.com/paper/2301.02039/) (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)
- [Invariance-Aware Randomized Smoothing Certificates](https://mlsanity.com/paper/2211.14207/) (2022)
- [Elliptical Attention](https://mlsanity.com/paper/2406.13770/) (2024)
- [Smoothed Embeddings for Certified Few-Shot Learning](https://mlsanity.com/paper/2202.01186/) (2022)
- [A Certified Radius-Guided Attack Framework to Image Segmentation Models](https://mlsanity.com/paper/2304.02693/) (2023)
- [RS-Reg: Probabilistic and Robust Certified Regression Through Randomized Smoothing](https://mlsanity.com/paper/2405.08892/) (2024)
- [Rethinking Randomized Smoothing from the Perspective of Scalability](https://mlsanity.com/paper/2312.12608/) (2023)
- [Towards Evading the Limits of Randomized Smoothing: A Theoretical Analysis](https://mlsanity.com/paper/2206.01715/) (2022)
- [Towards Better Certified Segmentation via Diffusion Models](https://mlsanity.com/paper/2306.09949/) (2023)
- [Bridging the Theoretical Gap in Randomized Smoothing](https://mlsanity.com/paper/2504.02412/) (2025)
- [Reconcile Certified Robustness and Accuracy for DNN-based Smoothed Majority Vote Classifier](https://mlsanity.com/paper/2509.25979/) (2025)
- [Integrating uncertainty quantification into randomized smoothing based robustness guarantees](https://mlsanity.com/paper/2410.20432/) (2024)
- [Explainability and Robustness of Deep Visual Classification Models](https://mlsanity.com/paper/2301.01343/) (2023)

## Abstract (arXiv)

Randomized smoothing is a recently proposed defense against adversarial attacks that has achieved SOTA provable robustness against ℓ2 perturbations. A number of publications have extended the guarantees to other metrics, such as ℓ1 or ℓ_∞, by using different smoothing measures. Although the current framework has been shown to yield near-optimal ℓp radii, the total safety region certified by the current framework can be arbitrarily small compared to the optimal. In this work, we propose a framework to improve the certified safety region for these smoothed classifiers without changing the underlying smoothing scheme. The theoretical contributions are as follows: 1) We generalize the certification for randomized smoothing by reformulating certified radius calculation as a nested optimization problem over a class of functions. 2) We provide a method to calculate the certified safety region using 0th-order and 1st-order information for Gaussian-smoothed classifiers. We also provide a framework that generalizes the calculation for certification using higher-order information. 3) We design efficient, high-confidence estimators for the relevant statistics of the first-order information. Combining the theoretical contribution 2) and 3) allows us to certify safety region that are significantly larger than the ones provided by the current methods. On CIFAR10 and Imagenet datasets, the new regions certified by our approach achieve significant improvements on general ℓ1 certified radii and on the ℓ2 certified radii for color-space attacks (ℓ2 restricted to 1 channel) while also achieving smaller improvements on the general ℓ2 certified radii. Our framework can also provide a way to circumvent the current impossibility results on achieving higher magnitude of certified radii without requiring the use of data-dependent smoothing techniques.