Verifiable Boosted Tree Ensembles
Stefano Calzavara Lorenzo Cazzaro Claudio Lucchese Giulio Ermanno Pibiri
Verifiable learning advocates for training machine learning models amenable
to efficient security verification. Prior research demonstrated that specific
classes of decision tree ensembles -- called large-spread ensembles -- allow
for robustness verification in polynomial time against any norm-based attacker.
This study expands prior work on verifiable learning from basic ensemble
methods (i.e., hard majority voting) to advanced boosted tree ensembles, such
as those trained using XGBoost or LightGBM. Our formal results indicate that
robustness verification is achievable in polynomial time when considering
attackers based on the $L_\infty$-norm, but remains NP-hard for other
norm-based attackers. Nevertheless, we present a pseudo-polynomial time
algorithm to verify robustness against attackers based on the $L_p$-norm for
any $p \in \mathbb{N} \cup \{0\}$, which in practice grants excellent
performance. Our experimental evaluation shows that large-spread boosted
ensembles are accurate enough for practical adoption, while being amenable to
efficient security verification.