Provably Robust Boosted Decision Stumps and Trees against Adversarial Attacks

Abstract

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 \textit{exact} min-max robust loss and test error for an $l_{\infty }$-attack can be computed in $O(T\log 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(n^{2}T\log 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 ${\epsilon }_{\infty }=0.3$), FMNIST (23.2% for ${\epsilon }_{\infty }=0.1$), and CIFAR-10 (74.7% for ${\epsilon }_{\infty }=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

Camera-ready version (accepted at NeurIPS 2019)

References in corpus (21)

• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples
• Certified Defenses against Adversarial Examples
• Robustness May Be at Odds with Accuracy
• Evaluating Robustness of Neural Networks with Mixed Integer Programming
• Black-box Adversarial Attacks with Limited Queries and Information
• On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models
• Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers
• NO Need to Worry about Adversarial Examples in Object Detection in Autonomous Vehicles
• Efficient Formal Safety Analysis of Neural Networks
• Simple Black-box Adversarial Attacks
• Training for Faster Adversarial Robustness Verification via Inducing ReLU Stability
• Query-Efficient Hard-label Black-box Attack:An Optimization-based Approach
• A more robust boosting algorithm
• Training verified learners with learned verifiers
• Evaluating and Understanding the Robustness of Adversarial Logit Pairing
• Provable Robustness of ReLU networks via Maximization of Linear Regions
• Do Deep Generative Models Know What They Don't Know?
• Logit Pairing Methods Can Fool Gradient-Based Attacks
• Evading classifiers in discrete domains with provable optimality guarantees
• Analysis and Optimization of Loss Functions for Multiclass, Top-k, and Multilabel Classification

Cited by in corpus (5)

• Not All Datasets Are Born Equal: On Heterogeneous Data and Adversarial Examples
• Cost-Aware Robust Tree Ensembles for Security Applications
• An Efficient Adversarial Attack for Tree Ensembles
• What it Thinks is Important is Important: Robustness Transfers through Input Gradients
• When are Non-Parametric Methods Robust?