The problem of adversarial samples has been studied extensively for neural networks. However, for boosting, in particular boosted decision trees and decision stumps there are almost no results, even though boosted decision trees, as e.g. XGBoost, are quite popular due to their interpretability and good prediction performance. We show in this paper that for boosted decision stumps the exact min-max optimal robust loss and test error for an $l_\infty$-attack can be computed in $O(n\,T\log T)$, where $T$ is the number of decision stumps and $n$ the number of data points, as well as an optimal update of the ensemble in $O(n^2\,T\log T)$. While not exact, we show how to optimize an upper bound on the robust loss for boosted trees. Up to our knowledge, these are the first algorithms directly optimizing provable robustness guarantees in the area of boosting. We make the code of all our experiments publicly available at https://github.com/max-andr/provably-robust-boosting

本文研究了提升决策树和决策桩的对抗性稳健性问题，并提出了一种快速计算精确的min-max鲁棒损失和测试误差的方法，并给出了一个高效的集成优化算法；同时，为提升树提出了一种基于上界的对稳健损失的优化算法，该方法在MNIST，FMNIST和CIFAR-10数据集上均取得了领先的稳健测试误差率，竞争力可与可证稳健卷积网络媲美。

可证明鲁棒性提升的决策树与决策桩抵御对抗攻击