# Provably Robust Boosted Decision Stumps and Trees against Adversarial Attacks

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

## Key facts

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

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

- [Robustness of Graph Neural Networks at Scale](https://mlsanity.com/paper/2110.14038/) (2021)
- [T-Miner: A Generative Approach to Defend Against Trojan Attacks on DNN-based Text Classification](https://mlsanity.com/paper/2103.04264/) (2021)
- [A Review of Formal Methods applied to Machine Learning](https://mlsanity.com/paper/2104.02466/) (2021)
- [Certifying Robustness to Programmable Data Bias in Decision Trees](https://mlsanity.com/paper/2110.04363/) (2021)
- [Connecting Interpretability and Robustness in Decision Trees through Separation](https://mlsanity.com/paper/2102.07048/) (2021)
- [Adversarial Robustness for Tabular Data through Cost and Utility Awareness](https://mlsanity.com/paper/2208.13058/) (2022)
- [Being Properly Improper](https://mlsanity.com/paper/2106.09920/) (2021)
- [Learning Decision Trees and Forests with Algorithmic Recourse](https://mlsanity.com/paper/2406.01098/) (2024)
- [A Multiclass Boosting Framework for Achieving Fast and Provable Adversarial Robustness](https://mlsanity.com/paper/2103.01276/) (2021)
- [(De-)Randomized Smoothing for Decision Stump Ensembles](https://mlsanity.com/paper/2205.13909/) (2022)
- [Fair Training of Decision Tree Classifiers](https://mlsanity.com/paper/2101.00909/) (2021)
- [SoK: Privacy-Preserving Collaborative Tree-based Model Learning](https://mlsanity.com/paper/2103.08987/) (2021)
- [Beyond Robustness: Resilience Verification of Tree-Based Classifiers](https://mlsanity.com/paper/2112.02705/) (2021)
- [A Scalable, Interpretable, Verifiable & Differentiable Logic Gate Convolutional Neural Network Architecture From Truth Tables](https://mlsanity.com/paper/2208.08609/) (2022)
- [Enhancing Robustness of Gradient-Boosted Decision Trees through One-Hot Encoding and Regularization](https://mlsanity.com/paper/2304.13761/) (2023)
- [Verifiable Learning for Robust Tree Ensembles](https://mlsanity.com/paper/2305.03626/) (2023)
- [Provably Adversarially Robust Nearest Prototype Classifiers](https://mlsanity.com/paper/2207.07208/) (2022)
- [Transferable Adversarial Robustness for Categorical Data via Universal Robust Embeddings](https://mlsanity.com/paper/2306.04064/) (2023)
- [Interpretable Differencing of Machine Learning Models](https://mlsanity.com/paper/2306.06473/) (2023)
- [Faster Repeated Evasion Attacks in Tree Ensembles](https://mlsanity.com/paper/2402.08586/) (2024)
- [Adversarial Example Detection in Deployed Tree Ensembles](https://mlsanity.com/paper/2206.13083/) (2022)
- [Robust Boosting Forests with Richer Deep Feature Hierarchy](https://mlsanity.com/paper/2210.16451/) (2022)
- [Symmetry Defense Against XGBoost Adversarial Perturbation Attacks](https://mlsanity.com/paper/2308.05575/) (2023)
- [Verifiable Boosted Tree Ensembles](https://mlsanity.com/paper/2402.14988/) (2024)
- [On the Efficiency of Training Robust Decision Trees](https://mlsanity.com/paper/2507.10048/) (2025)
- [Kernel of Partition Paths: A Unified Representation for Tree Ensembles](https://mlsanity.com/paper/2606.18853/) (2026)

## Abstract (arXiv)

The problem of adversarial robustness has been studied extensively for neural networks. However, for boosted decision trees and decision stumps there are almost no results, even though they are widely used in practice (e.g. XGBoost) due to their accuracy, interpretability, and efficiency. We show in this paper that for boosted decision stumps the textitexact min-max robust loss and test error for an l_∞-attack can be computed in O(Tlog T) time per input, where T is the number of decision stumps and the optimal update step of the ensemble can be done in O(n2,Tlog T), where n is the number of data points. For boosted trees we show how to efficiently calculate and optimize an upper bound on the robust loss, which leads to state-of-the-art robust test error for boosted trees on MNIST (12.5% for ε_∞=0.3), FMNIST (23.2% for ε_∞=0.1), and CIFAR-10 (74.7% for ε_∞=8/255). Moreover, the robust test error rates we achieve are competitive to the ones of provably robust convolutional networks. The code of all our experiments is available at http://github.com/max-andr/provably-robust-boosting