# Treatment of Statistical Estimation Problems in Randomized Smoothing for Adversarial Robustness

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 35 references that are in the map.
- First posted on arXiv 25 Jun 2024.

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

- [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)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers](https://mlsanity.com/paper/1906.04584/) (2019)
- [Estimating means of bounded random variables by betting](https://mlsanity.com/paper/2010.09686/) (2020)
- [Randomized Smoothing of All Shapes and Sizes](https://mlsanity.com/paper/2002.08118/) (2020)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [(De)Randomized Smoothing for Certifiable Defense against Patch Attacks](https://mlsanity.com/paper/2002.10733/) (2020)
- [Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers](https://mlsanity.com/paper/1906.04948/) (2019)
- [Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More](https://mlsanity.com/paper/2008.12952/) (2020)
- [Boosting Randomized Smoothing with Variance Reduced Classifiers](https://mlsanity.com/paper/2106.06946/) (2021)
- [Tight Concentrations and Confidence Sequences from the Regret of Universal Portfolio](https://mlsanity.com/paper/2110.14099/) (2021)
- [Improved, Deterministic Smoothing for L_1 Certified Robustness](https://mlsanity.com/paper/2103.10834/) (2021)
- [Incremental Randomized Smoothing Certification](https://mlsanity.com/paper/2305.19521/) (2023)
- [Input-Specific Robustness Certification for Randomized Smoothing](https://mlsanity.com/paper/2112.12084/) (2021)
- [On Confidence Sequences for Bounded Random Processes via Universal Gambling Strategies](https://mlsanity.com/paper/2207.12382/) (2022)
- [Gambling-Based Confidence Sequences for Bounded Random Vectors](https://mlsanity.com/paper/2402.03683/) (2024)

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

- [Bridging the Theoretical Gap in Randomized Smoothing](https://mlsanity.com/paper/2504.02412/) (2025)
- [STaR-Bets: Sequential Target-Recalculating Bets for Tighter Confidence Intervals](https://mlsanity.com/paper/2505.22422/) (2025)
- [Randomized Smoothing Meets Vision-Language Models](https://mlsanity.com/paper/2509.16088/) (2025)
- [Contract And Conquer: How to Provably Compute Adversarial Examples for a Black-Box Model?](https://mlsanity.com/paper/2603.10689/) (2026)
- [Laplace-Bridged Randomized Smoothing for Fast Certified Robustness](https://mlsanity.com/paper/2604.24993/) (2026)
- [RRISE: Robust Radius Inference via a Surrogate Estimator](https://mlsanity.com/paper/2606.02876/) (2026)
- [Halt Fast! Early Stopping for Certified Robustness](https://mlsanity.com/paper/2606.27694/) (2026)
- [What Was That Again? Certified Robustness for Automatic Speech Recognition](https://mlsanity.com/paper/2606.27698/) (2026)

## Abstract (arXiv)

Randomized smoothing is a popular certified defense against adversarial attacks. In its essence, we need to solve a problem of statistical estimation which is usually very time-consuming since we need to perform numerous (usually 105) forward passes of the classifier for every point to be certified. In this paper, we review the statistical estimation problems for randomized smoothing to find out if the computational burden is necessary. In particular, we consider the (standard) task of adversarial robustness where we need to decide if a point is robust at a certain radius or not using as few samples as possible while maintaining statistical guarantees. We present estimation procedures employing confidence sequences enjoying the same statistical guarantees as the standard methods, with the optimal sample complexities for the estimation task and empirically demonstrate their good performance. Additionally, we provide a randomized version of Clopper-Pearson confidence intervals resulting in strictly stronger certificates.