On $\ell_p$-norm Robustness of Ensemble Stumps and Trees
- URL: http://arxiv.org/abs/2008.08755v2
- Date: Tue, 29 Sep 2020 06:13:02 GMT
- Title: On $\ell_p$-norm Robustness of Ensemble Stumps and Trees
- Authors: Yihan Wang, Huan Zhang, Hongge Chen, Duane Boning, Cho-Jui Hsieh
- Abstract summary: 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.
- Score: 83.81523991945018
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
Related papers
- Identifying General Mechanism Shifts in Linear Causal Representations [58.6238439611389]
We consider the linear causal representation learning setting where we observe a linear mixing of $d$ unknown latent factors.
Recent work has shown that it is possible to recover the latent factors as well as the underlying structural causal model over them.
We provide a surprising identifiability result that it is indeed possible, under some very mild standard assumptions, to identify the set of shifted nodes.
arXiv Detail & Related papers (2024-10-31T15:56:50Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$.
We first design novel efficient algorithms to privately release pair-wise cosine similarities.
We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
arXiv Detail & Related papers (2024-06-07T12:07:16Z) - Verifiable Boosted Tree Ensembles [7.107477567356262]
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.
arXiv Detail & Related papers (2024-02-22T21:56:20Z) - Certified Adversarial Robustness Within Multiple Perturbation Bounds [38.3813286696956]
Randomized smoothing (RS) is a well known certified defense against adversarial attacks.
In this work, we aim to improve the certified adversarial robustness against multiple perturbation bounds simultaneously.
arXiv Detail & Related papers (2023-04-20T16:42:44Z) - Minimax Rates for Robust Community Detection [19.229475414802213]
We study the problem of community detection in the block model with adversarial node corruptions.
Our main result is an efficient algorithm that can tolerate an $epsilon$-fraction of corruptions and unbounded error $O(epsilon) + e-fracC2 (1 pm o(1))$ where $C = (sqrta - sqrtb)2$ is the signal-to-noise ratio.
We show that our algorithms are doubly-robust in the sense that they work in an even more
arXiv Detail & Related papers (2022-07-25T04:45:16Z) - Unbiased and Efficient Sampling of Dependency Trees [0.0]
Most treebanks require that every valid dependency tree has a single edge coming out of the ROOT node.
Zmigrod et al. have recently proposed algorithms for sampling with and without replacement from the single-root dependency tree distribution.
We show that their fastest algorithm for sampling with replacement, Wilson-RC, is in fact biased.
arXiv Detail & Related papers (2022-05-25T09:57:28Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
We study the linear contextual bandit problem in the presence of adversarial corruption.
We present a variance-aware algorithm that is adaptive to the level of adversarial contamination $C$.
arXiv Detail & Related papers (2021-10-25T02:53:24Z) - Learning stochastic decision trees [19.304587350775385]
We give a quasipolynomial-time algorithm for learning decision trees that is optimally resilient to adversarial noise.
Our algorithm is furthermore proper, returning a hypothesis that is itself a decision tree.
arXiv Detail & Related papers (2021-05-08T04:54:12Z) - Towards Defending Multiple $\ell_p$-norm Bounded Adversarial
Perturbations via Gated Batch Normalization [120.99395850108422]
Existing adversarial defenses typically improve model robustness against individual specific perturbations.
Some recent methods improve model robustness against adversarial attacks in multiple $ell_p$ balls, but their performance against each perturbation type is still far from satisfactory.
We propose Gated Batch Normalization (GBN) to adversarially train a perturbation-invariant predictor for defending multiple $ell_p bounded adversarial perturbations.
arXiv Detail & Related papers (2020-12-03T02:26:01Z) - An Efficient Adversarial Attack for Tree Ensembles [91.05779257472675]
adversarial attacks on tree based ensembles such as gradient boosting decision trees (DTs) and random forests (RFs)
We show that our method can be thousands of times faster than the previous mixed-integer linear programming (MILP) based approach.
Our code is available at https://chong-z/tree-ensemble-attack.
arXiv Detail & Related papers (2020-10-22T10:59:49Z)
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.