On $\ell_p$-norm Robustness of Ensemble Stumps and Trees
  Recent papers have demonstrated that ensemble stumps and trees could be
vulnerable to small input perturbations, so robustness verification and defense
for those models have become an important research problem. However, due to the
structure of decision trees, where each node makes decision purely based on one
feature value, all the previous works only consider the $\ell_\infty$ norm
perturbation. To study robustness with respect to a general $\ell_p$ norm
perturbation, one has to consider the correlation between perturbations on
different features, which has not been handled by previous algorithms. In this
paper, we study the problem of robustness verification and certified defense
with respect to general $\ell_p$ norm perturbations for ensemble decision
stumps and trees. For robustness verification of ensemble stumps, we prove that
complete verification is NP-complete for $p\in(0, \infty)$ while polynomial
time algorithms exist for $p=0$ or $\infty$. For $p\in(0, \infty)$ we develop
an efficient dynamic programming based algorithm for sound verification of
ensemble stumps. For ensemble trees, we generalize the previous multi-level
robustness verification algorithm to $\ell_p$ norm. We demonstrate the first
certified defense method for training ensemble stumps and trees with respect to
$\ell_p$ norm perturbations, and verify its effectiveness empirically on real
datasets.
