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.

可验证学习通过训练机器学习模型实现高效的安全验证，该研究从基本集成方法扩展到高级增强树集成，证明了多项式时间内对某些攻击者的强健性验证是可实现的，但对于其他基于范数的攻击者仍然是 NP - 难的。

可验证的增强树集合

Verifiable Boosted Tree Ensembles

Verifying the robustness of machine learning models against evasion attacks
at test time is an important research problem. Unfortunately, prior work
established that this problem is NP-hard for decision tree ensembles, hence
bound to be intractable for specific inputs. In this paper, we identify a
restricted class of decision tree ensembles, called large-spread ensembles,
which admit a security verification algorithm running in polynomial time. We
then propose a new approach called verifiable learning, which advocates the
training of such restricted model classes which are amenable for efficient
verification. We show the benefits of this idea by designing a new training
algorithm that automatically learns a large-spread decision tree ensemble from
labelled data, thus enabling its security verification in polynomial time.
Experimental results on publicly available datasets confirm that large-spread
ensembles trained using our algorithm can be verified in a matter of seconds,
using standard commercial hardware. Moreover, large-spread ensembles are more
robust than traditional ensembles against evasion attacks, while incurring in
just a relatively small loss of accuracy in the non-adversarial setting.

本文提出了一种叫做可验证学习的方法用以解决机器学习模型在测试阶段对抗攻击的安全验证问题，并提出了一种新的训练算法以自动学习人工决策树集合。在公开数据集上的实验结果证实，这种方法可以在标准的商业硬件上在几秒钟内验证其使用我们算法训练的大规模分布型集合，而且相对于传统集合，大规模分布型集合对于对抗攻击更具鲁棒性，而在非对抗环境下只会受到相对较小的精度损失。