# (De-)Randomized Smoothing for Decision Stump Ensembles

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 80 references that are in the map.
- First posted on arXiv 27 May 2022.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [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)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Tabular Data: Deep Learning is Not All You Need](https://mlsanity.com/paper/2106.03253/) (2021)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (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)
- [Adversarial Training and Robustness for Multiple Perturbations](https://mlsanity.com/paper/1904.13000/) (2019)
- [Certified Adversarial Robustness with Additive Noise](https://mlsanity.com/paper/1809.03113/) (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)
- [Towards the first adversarially robust neural network model on MNIST](https://mlsanity.com/paper/1805.09190/) (2018)
- [(De)Randomized Smoothing for Certifiable Defense against Patch Attacks](https://mlsanity.com/paper/2002.10733/) (2020)
- [PRIMA: General and Precise Neural Network Certification via Scalable Convex Hull Approximations](https://mlsanity.com/paper/2103.03638/) (2021)
- [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)
- [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 Robustness of Graph Neural Networks against Adversarial Structural Perturbation](https://mlsanity.com/paper/2008.10715/) (2020)
- [Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More](https://mlsanity.com/paper/2008.12952/) (2020)
- [Certified Robustness for Top-k Predictions against Adversarial Perturbations via Randomized Smoothing](https://mlsanity.com/paper/1912.09899/) (2019)
- [Certified Defense to Image Transformations via Randomized Smoothing](https://mlsanity.com/paper/2002.12463/) (2020)
- [TSS: Transformation-Specific Smoothing for Robustness Certification](https://mlsanity.com/paper/2002.12398/) (2020)

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

- [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)
- [Data-Aware and Scalable Sensitivity Analysis for Decision Tree Ensembles](https://mlsanity.com/paper/2602.07453/) (2026)
- [Verifiable Boosted Tree Ensembles](https://mlsanity.com/paper/2402.14988/) (2024)
- [PDA: Text-Augmented Defense Framework for Robust Vision-Language Models against Adversarial Image Attacks](https://mlsanity.com/paper/2604.01010/) (2026)

## Abstract (arXiv)

Tree-based models are used in many high-stakes application domains such as finance and medicine, where robustness and interpretability are of utmost importance. Yet, methods for improving and certifying their robustness are severely under-explored, in contrast to those focusing on neural networks. Targeting this important challenge, we propose deterministic smoothing for decision stump ensembles. Whereas most prior work on randomized smoothing focuses on evaluating arbitrary base models approximately under input randomization, the key insight of our work is that decision stump ensembles enable exact yet efficient evaluation via dynamic programming. Importantly, we obtain deterministic robustness certificates, even jointly over numerical and categorical features, a setting ubiquitous in the real world. Further, we derive an MLE-optimal training method for smoothed decision stumps under randomization and propose two boosting approaches to improve their provable robustness. An extensive experimental evaluation on computer vision and tabular data tasks shows that our approach yields significantly higher certified accuracies than the state-of-the-art for tree-based models. We release all code and trained models at https://github.com/eth-sri/drs.