# Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers

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

## Key facts

- Cited by 65 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2019.

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

- [PatchCleanser: Certifiably Robust Defense against Adversarial Patches for Any Image Classifier](https://mlsanity.com/paper/2108.09135/) (2021)
- [PointGuard: Provably Robust 3D Point Cloud Classification](https://mlsanity.com/paper/2103.03046/) (2021)
- [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)
- [CROP: Certifying Robust Policies for Reinforcement Learning through Functional Smoothing](https://mlsanity.com/paper/2106.09292/) (2021)
- [Improved, Deterministic Smoothing for L_1 Certified Robustness](https://mlsanity.com/paper/2103.10834/) (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)
- [How does Heterophily Impact the Robustness of Graph Neural Networks? Theoretical Connections and Practical Implications](https://mlsanity.com/paper/2106.07767/) (2021)
- [StyleFool: Fooling Video Classification Systems via Style Transfer](https://mlsanity.com/paper/2203.16000/) (2022)
- [BagFlip: A Certified Defense against Data Poisoning](https://mlsanity.com/paper/2205.13634/) (2022)
- [Center Smoothing: Certified Robustness for Networks with Structured Outputs](https://mlsanity.com/paper/2102.09701/) (2021)
- [RS-Del: Edit Distance Robustness Certificates for Sequence Classifiers via Randomized Deletion](https://mlsanity.com/paper/2302.01757/) (2023)
- [Collective Robustness Certificates: Exploiting Interdependence in Graph Neural Networks](https://mlsanity.com/paper/2302.02829/) (2023)
- [Advancing the Robustness of Large Language Models through Self-Denoised Smoothing](https://mlsanity.com/paper/2404.12274/) (2024)
- [Robust Yet Efficient Conformal Prediction Sets](https://mlsanity.com/paper/2407.09165/) (2024)
- [Unveiling the Basin-Like Loss Landscape in Large Language Models](https://mlsanity.com/paper/2505.17646/) (2025)
- [Incremental Randomized Smoothing Certification](https://mlsanity.com/paper/2305.19521/) (2023)
- [Input-agnostic Certified Group Fairness via Gaussian Parameter Smoothing](https://mlsanity.com/paper/2206.11423/) (2022)
- [Projected Randomized Smoothing for Certified Adversarial Robustness](https://mlsanity.com/paper/2309.13794/) (2023)
- [UniCR: Universally Approximated Certified Robustness via Randomized Smoothing](https://mlsanity.com/paper/2207.02152/) (2022)
- [CARE: Certifiably Robust Learning with Reasoning via Variational Inference](https://mlsanity.com/paper/2209.05055/) (2022)
- [Localized Randomized Smoothing for Collective Robustness Certification](https://mlsanity.com/paper/2210.16140/) (2022)
- [Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networks](https://mlsanity.com/paper/2301.02039/) (2023)
- [MultiGuard: Provably Robust Multi-label Classification against Adversarial Examples](https://mlsanity.com/paper/2210.01111/) (2022)
- [Confidence-aware Training of Smoothed Classifiers for Certified Robustness](https://mlsanity.com/paper/2212.09000/) (2022)
- [It Is All About Data: A Survey on the Effects of Data on Adversarial Robustness](https://mlsanity.com/paper/2303.09767/) (2023)
- [Hierarchical Randomized Smoothing](https://mlsanity.com/paper/2310.16221/) (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)

## Abstract (arXiv)

Strong theoretical guarantees of robustness can be given for ensembles of classifiers generated by input randomization. Specifically, an ℓ2 bounded adversary cannot alter the ensemble prediction generated by an additive isotropic Gaussian noise, where the radius for the adversary depends on both the variance of the distribution as well as the ensemble margin at the point of interest. We build on and considerably expand this work across broad classes of distributions. In particular, we offer adversarial robustness guarantees and associated algorithms for the discrete case where the adversary is ℓ0 bounded. Moreover, we exemplify how the guarantees can be tightened with specific assumptions about the function class of the classifier such as a decision tree. We empirically illustrate these results with and without functional restrictions across image and molecule datasets.