Verifiable Boosted Tree Ensembles
- URL: http://arxiv.org/abs/2402.14988v1
- Date: Thu, 22 Feb 2024 21:56:20 GMT
- Title: Verifiable Boosted Tree Ensembles
- Authors: Stefano Calzavara, Lorenzo Cazzaro, Claudio Lucchese, Giulio Ermanno
Pibiri
- Abstract summary: Verifiable learning advocates for training machine learning models amenable to efficient security verification.
This study expands prior work on verifiable learning from basic ensemble methods.
We present a pseudo-polynomial time algorithm to verify robustness against attackers based on the $L_in$-norm.
- Score: 7.107477567356262
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
Related papers
- Multiclass Boosting: Simple and Intuitive Weak Learning Criteria [72.71096438538254]
We give a simple and efficient boosting algorithm, that does not require realizability assumptions.
We present a new result on boosting for list learners, as well as provide a novel proof for the characterization of multiclass PAC learning.
arXiv Detail & Related papers (2023-07-02T19:26:58Z) - Verifiable Learning for Robust Tree Ensembles [8.207928136395184]
A class of decision tree ensembles called large-spread ensembles admit a security verification algorithm running in restricted time.
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.
Experimental results on public datasets confirm that large-spread ensembles trained using our algorithm can be verified in a matter of seconds.
arXiv Detail & Related papers (2023-05-05T15:37:23Z) - A Stable, Fast, and Fully Automatic Learning Algorithm for Predictive
Coding Networks [65.34977803841007]
Predictive coding networks are neuroscience-inspired models with roots in both Bayesian statistics and neuroscience.
We show how by simply changing the temporal scheduling of the update rule for the synaptic weights leads to an algorithm that is much more efficient and stable than the original one.
arXiv Detail & Related papers (2022-11-16T00:11:04Z) - Adversarial Vulnerability of Randomized Ensembles [12.082239973914326]
We show that randomized ensembles are more vulnerable to imperceptible adversarial perturbations than even standard AT models.
We propose a theoretically-sound and efficient adversarial attack algorithm (ARC) capable of compromising random ensembles even in cases where adaptive PGD fails to do so.
arXiv Detail & Related papers (2022-06-14T10:37:58Z) - Scalable Whitebox Attacks on Tree-based Models [2.3186641356561646]
This paper proposes a novel whitebox adversarial robustness testing approach for tree ensemble models.
By leveraging sampling and the log-derivative trick, the proposed approach can scale up to testing tasks that were previously unmanageable.
arXiv Detail & Related papers (2022-03-31T21:36:20Z) - Policy Smoothing for Provably Robust Reinforcement Learning [109.90239627115336]
We study the provable robustness of reinforcement learning against norm-bounded adversarial perturbations of the inputs.
We generate certificates that guarantee that the total reward obtained by the smoothed policy will not fall below a certain threshold under a norm-bounded adversarial of perturbation the input.
arXiv Detail & Related papers (2021-06-21T21:42:08Z) - Robustness, Privacy, and Generalization of Adversarial Training [84.38148845727446]
This paper establishes and quantifies the privacy-robustness trade-off and generalization-robustness trade-off in adversarial training.
We show that adversarial training is $(varepsilon, delta)$-differentially private, where the magnitude of the differential privacy has a positive correlation with the robustified intensity.
Our generalization bounds do not explicitly rely on the parameter size which would be large in deep learning.
arXiv Detail & Related papers (2020-12-25T13:35:02Z) - On $\ell_p$-norm Robustness of Ensemble Stumps and Trees [83.81523991945018]
We develop an efficient programming based algorithm for sound verification of ensemble stumps.
We demonstrate the first certified defense method for training ensemble stumps and trees with respect to $ell_p$ norm perturbations.
arXiv Detail & Related papers (2020-08-20T03:42:40Z) - Regularized Training and Tight Certification for Randomized Smoothed
Classifier with Provable Robustness [15.38718018477333]
We derive a new regularized risk, in which the regularizer can adaptively encourage the accuracy and robustness of the smoothed counterpart.
We also design a new certification algorithm, which can leverage the regularization effect to provide tighter robustness lower bound that holds with high probability.
arXiv Detail & Related papers (2020-02-17T20:54:34Z) - Certified Robustness to Label-Flipping Attacks via Randomized Smoothing [105.91827623768724]
Machine learning algorithms are susceptible to data poisoning attacks.
We present a unifying view of randomized smoothing over arbitrary functions.
We propose a new strategy for building classifiers that are pointwise-certifiably robust to general data poisoning attacks.
arXiv Detail & Related papers (2020-02-07T21:28:30Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.