# Boosting Randomized Smoothing with Variance Reduced Classifiers

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

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- Builds on 48 of its 82 references that are in the map.
- First posted on arXiv 13 Jun 2021.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [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)
- [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)
- [Adversarial Machine Learning at Scale](https://mlsanity.com/paper/1611.01236/) (2016)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [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)
- [On Adaptive Attacks to Adversarial Example Defenses](https://mlsanity.com/paper/2002.08347/) (2020)
- [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)
- [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)
- [Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks](https://mlsanity.com/paper/1705.01320/) (2017)
- [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)
- [Efficient Formal Safety Analysis of Neural Networks](https://mlsanity.com/paper/1809.08098/) (2018)
- [Randomized Smoothing of All Shapes and Sizes](https://mlsanity.com/paper/2002.08118/) (2020)
- [MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radius](https://mlsanity.com/paper/2001.02378/) (2020)
- [Decoupling Direction and Norm for Efficient Gradient-Based L2 Adversarial Attacks and Defenses](https://mlsanity.com/paper/1811.09600/) (2018)
- [Certified Robustness to Label-Flipping Attacks via Randomized Smoothing](https://mlsanity.com/paper/2002.03018/) (2020)
- [(De)Randomized Smoothing for Certifiable Defense against Patch Attacks](https://mlsanity.com/paper/2002.10733/) (2020)
- [Consistency Regularization for Certified Robustness of Smoothed Classifiers](https://mlsanity.com/paper/2006.04062/) (2020)
- [Enabling certification of verification-agnostic networks via memory-efficient semidefinite programming](https://mlsanity.com/paper/2010.11645/) (2020)

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

- [(Certified!!) Adversarial Robustness for Free!](https://mlsanity.com/paper/2206.10550/) (2022)
- [DensePure: Understanding Diffusion Models towards Adversarial Robustness](https://mlsanity.com/paper/2211.00322/) (2022)
- [Boosting the Certified Robustness of L-infinity Distance Nets](https://mlsanity.com/paper/2110.06850/) (2021)
- [Your Diffusion Model is Secretly a Certifiably Robust Classifier](https://mlsanity.com/paper/2402.02316/) (2024)
- [Denoising Masked AutoEncoders Help Robust Classification](https://mlsanity.com/paper/2210.06983/) (2022)
- [DiffSmooth: Certifiably Robust Learning via Diffusion Models and Local Smoothing](https://mlsanity.com/paper/2308.14333/) (2023)
- [CC-Cert: A Probabilistic Approach to Certify General Robustness of Neural Networks](https://mlsanity.com/paper/2109.10696/) (2021)
- [Mitigating the Curse of Dimensionality for Certified Robustness via Dual Randomized Smoothing](https://mlsanity.com/paper/2404.09586/) (2024)
- [Incremental Randomized Smoothing Certification](https://mlsanity.com/paper/2305.19521/) (2023)
- [XRand: Differentially Private Defense against Explanation-Guided Attacks](https://mlsanity.com/paper/2212.04454/) (2022)
- [TAPS: Connecting Certified and Adversarial Training](https://mlsanity.com/paper/2305.04574/) (2023)
- [Revisiting Deep Ensemble for Out-of-Distribution Detection: A Loss Landscape Perspective](https://mlsanity.com/paper/2310.14227/) (2023)
- [Hierarchical Randomized Smoothing](https://mlsanity.com/paper/2310.16221/) (2023)
- [Multi-scale Diffusion Denoised Smoothing](https://mlsanity.com/paper/2310.16779/) (2023)
- [The Lipschitz-Variance-Margin Tradeoff for Enhanced Randomized Smoothing](https://mlsanity.com/paper/2309.16883/) (2023)
- [Treatment of Statistical Estimation Problems in Randomized Smoothing for Adversarial Robustness](https://mlsanity.com/paper/2406.17830/) (2024)
- [Augment then Smooth: Reconciling Differential Privacy with Certified Robustness](https://mlsanity.com/paper/2306.08656/) (2023)
- [(De-)Randomized Smoothing for Decision Stump Ensembles](https://mlsanity.com/paper/2205.13909/) (2022)
- [Gaussian Loss Smoothing Enables Certified Training with Tight Convex Relaxations](https://mlsanity.com/paper/2403.07095/) (2024)
- [SPLITZ: Certifiable Robustness via Split Lipschitz Randomized Smoothing](https://mlsanity.com/paper/2407.02811/) (2024)
- [Few-shot Classification via Ensemble Learning with Multi-Order Statistics](https://mlsanity.com/paper/2305.00454/) (2023)
- [Rethinking Randomized Smoothing from the Perspective of Scalability](https://mlsanity.com/paper/2312.12608/) (2023)
- [Multi-head Ensemble of Smoothed Classifiers for Certified Robustness](https://mlsanity.com/paper/2211.10882/) (2022)
- [Certifying Ensembles: A General Certification Theory with S-Lipschitzness](https://mlsanity.com/paper/2304.13019/) (2023)
- [COMMIT: Certifying Robustness of Multi-Sensor Fusion Systems against Semantic Attacks](https://mlsanity.com/paper/2403.02329/) (2024)
- [Certifying Adapters: Enabling and Enhancing the Certification of Classifier Adversarial Robustness](https://mlsanity.com/paper/2405.16036/) (2024)
- [Consistency Purification: Effective and Efficient Diffusion Purification towards Certified Robustness](https://mlsanity.com/paper/2407.00623/) (2024)
- [AuditVotes: Elevating Provable Defense for GNNs with Efficient Augmentation and Conditional Smoothing](https://mlsanity.com/paper/2503.22998/) (2025)
- [Reconcile Certified Robustness and Accuracy for DNN-based Smoothed Majority Vote Classifier](https://mlsanity.com/paper/2509.25979/) (2025)
- [Smooth-Reduce: Leveraging Patches for Improved Certified Robustness](https://mlsanity.com/paper/2205.06154/) (2022)

## Abstract (arXiv)

Randomized Smoothing (RS) is a promising method for obtaining robustness certificates by evaluating a base model under noise. In this work, we: (i) theoretically motivate why ensembles are a particularly suitable choice as base models for RS, and (ii) empirically confirm this choice, obtaining state-of-the-art results in multiple settings. The key insight of our work is that the reduced variance of ensembles over the perturbations introduced in RS leads to significantly more consistent classifications for a given input. This, in turn, leads to substantially increased certifiable radii for samples close to the decision boundary. Additionally, we introduce key optimizations which enable an up to 55-fold decrease in sample complexity of RS for predetermined radii, thus drastically reducing its computational overhead. Experimentally, we show that ensembles of only 3 to 10 classifiers consistently improve on their strongest constituting model with respect to their average certified radius (ACR) by 5% to 21% on both CIFAR10 and ImageNet, achieving a new state-of-the-art ACR of 0.86 and 1.11, respectively. We release all code and models required to reproduce our results at https://github.com/eth-sri/smoothing-ensembles.