# On the Efficiency of Training Robust Decision Trees

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 38 references that are in the map.
- First posted on arXiv 14 Jul 2025.

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

- [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)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Theoretically Principled Trade-off between Robustness and Accuracy](https://mlsanity.com/paper/1901.08573/) (2019)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Fast is better than free: Revisiting adversarial training](https://mlsanity.com/paper/2001.03994/) (2020)
- [Adversarial Examples Are Not Easily Detected: Bypassing Ten Detection Methods](https://mlsanity.com/paper/1705.07263/) (2017)
- [Understanding and Improving Fast Adversarial Training](https://mlsanity.com/paper/2007.02617/) (2020)
- [Evasion and Hardening of Tree Ensemble Classifiers](https://mlsanity.com/paper/1509.07892/) (2015)
- [Robust Decision Trees Against Adversarial Examples](https://mlsanity.com/paper/1902.10660/) (2019)
- [On the Certified Robustness for Ensemble Models and Beyond](https://mlsanity.com/paper/2107.10873/) (2021)
- [The SCIP Optimization Suite 9.0](https://mlsanity.com/paper/2402.17702/) (2024)
- [Robustness Verification of Tree-based Models](https://mlsanity.com/paper/1906.03849/) (2019)
- [Provably Robust Boosted Decision Stumps and Trees against Adversarial Attacks](https://mlsanity.com/paper/1906.03526/) (2019)
- [Efficient Training of Robust Decision Trees Against Adversarial Examples](https://mlsanity.com/paper/2012.10438/) (2020)
- [Adversarial Robustness for Tabular Data through Cost and Utility Awareness](https://mlsanity.com/paper/2208.13058/) (2022)
- [Treant: Training Evasion-Aware Decision Trees](https://mlsanity.com/paper/1907.01197/) (2019)
- [On the Robustness of Deep K-Nearest Neighbors](https://mlsanity.com/paper/1903.08333/) (2019)
- [An Efficient Adversarial Attack for Tree Ensembles](https://mlsanity.com/paper/2010.11598/) (2020)
- [Evading classifiers in discrete domains with provable optimality guarantees](https://mlsanity.com/paper/1810.10939/) (2018)
- [Towards Generating Adversarial Examples on Mixed-type Data](https://mlsanity.com/paper/2210.09405/) (2022)

## Abstract (arXiv)

As machine learning gets adopted into the industry quickly, trustworthiness is increasingly in focus. Yet, efficiency and sustainability of robust training pipelines still have to be established. In this work, we consider a simple pipeline for training adversarially robust decision trees and investigate the efficiency of each step. Our pipeline consists of three stages. Firstly, we choose the perturbation size automatically for each dataset. For that, we introduce a simple algorithm, instead of relying on intuition or prior work. Moreover, we show that the perturbation size can be estimated from smaller models than the one intended for full training, and thus significant gains in efficiency can be achieved. Secondly, we train state-of-the-art adversarial training methods and evaluate them regarding both their training time and adversarial accuracy. Thirdly, we certify the robustness of each of the models thus obtained and investigate the time required for this. We find that verification time, which is critical to the efficiency of the full pipeline, is not correlated with training time.