(De-)Randomized Smoothing for Decision Stump Ensembles
Authors: Miklós Z. Horváth
Mark Niklas Mueller
Marc Fischer
Martin Vechev
Venue: NeurIPS 2022 Accept (2022)
Keywords: adversarial robustness
certified robustness
randomized smoothing
tree-based models

Abstract: Tree-based models are used in many high-stakes application domains such as ﬁnance and medicine, where robustness and interpretability are of utmost importance. Yet, methods for improving and certifying their robustness are severely under-explored, in contrast to those focusing on neural networks. Targeting this important challenge, we propose deterministic smoothing for decision stump ensembles. Whereas most prior work on randomized smoothing focuses on evaluating arbitrary base models approximately under input randomization, the key insight of our work is that decision stump ensembles enable exact yet efﬁcient evaluation via dynamic programming. Importantly, we obtain deterministic robustness certiﬁcates, even jointly over numerical and categorical features, a setting ubiquitous in the real world. Further, we derive an MLE-optimal training method for smoothed decision stumps under randomization and propose two boosting approaches to improve their provable robustness. An extensive experimental evaluation on computer vision and tabular data tasks shows that our approach yields signiﬁcantly higher certiﬁed accuracies than the state-of-the-art for tree-based models. We release all code and trained models at https://github.com/eth-sri/drs.

(De-JRandomized Smoothing for Decision Stump Ensembles
Miklós Z. Horváth; Mark Niklas Müller, Mare Fischer, Martin Vechev
Department of Computer Science
ETH Zurich
Switzerland
mihorvat@ethz.ch {mark, mue mueller,mare fischer, martin. vechev)@inf.etth .wt.f.e.tccccc
Abstract
Tree-based models are used in many high-stakes application domains such as finance and medicine, where robustness and interpretability of utmost impor- tance. Yet, methods for improving and certifying their robustness are severely under-explored, in contrast those focusing neural networks. Targeting this important challenge, we propose deterministic smoothing for decision stump en- sembles. Whereas most prior work on randomized smoothing focuses evaluating arbitrary base models approximately under input randomization, the key insight of our work that decision stump ensembles enable exact yet efficient evaluation via dynamic programming, Importantly, we obtain deterministic robustness certificates, even jointly over numerical and categorical features, setting ubiquitous the real world. Further, we derive an MLE-optimal training method for smoothed decision stumps under randomization and propose two boosting approaches to improve their provable robustness. An extensive experimental evaluation on computer vision and tabular data tasks shows that our approach yields significantly higher certified accuracies than the state-of-the-arr for tree- tree-based models. We release all code and trained models at htttps://github..co cww/etoococoeeoeeoe sri/drs
Introduction
Tree-based models have long been a favourite for making decisions in high-stakes domains such medicine and finance, due their interpretability and exceptional performance tabular data []] However, recent results have highlighted that gree-based models are, similarly to other machine learning models 2 B. also highly susceptible adversarial examples (4 raising concerns about their use high-stakes domains where errors can have dire consequences.
While the robustness of neural models has received considerable attention 7 21 the challenge of obtaining robustness guarantees for ensembles of tree-based models has only been investigated recently [4 12, 23). However, these initial works only consider numerical features and are based on worst-case approximations, which do not scale well to the difficult E, f--norm setting.
This Work In this work, we address this challenge and present DRS, novel (De- Randmmaadd Smoothing approach, for constructing robust tree-based models with deterministic Ep fp-norm guarantees while supporting both categorical and numerical variables. Unlike prior work, our method is based on Randomized Smoothing (RS) 24], an approach that obtains robustness guarantees by evaluating general base model under an input randomization σ(x). However, in contrast to standard applications of RS, which use costly and imprecise approximations via sampling and only obtain probabilistic certificates, we leverage the structure of decision stump ensembles to compute their exact output
Equal contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

success probability Ps
f2(222
0.5
(0;
Natural Prediction
class
class
fs(s))
0.0
0.0
0.5
0.0
0.6
1.0
(a) Meta-Stumps
(b) PDFs
(c) Ensemble PDF
(d) Ensemble CDF
Figure I: Given ensemble of 3 meta-stumps fi (piecewise constant univariate functions), each operating on different feature 2, of an input obtain distribution over their outputs (b). Wc aggregate these individual PDFs via dynamic programming obtain the probability distribution over the ensemble's 's outputs (c). can then compute the corresponding CDF (d) to evaluate the smoothed Stump ensemble exactly.
calculate the prohability of every output under input randomization (a) to
distributions for a given input randomization scheme and thus obtain deterministic certificates. Our key insight is that this distribution can be efficiently computed by aggregating independent distributions associated with the individual features used by the ensemble.
We illustrate this idea in Fig. 1 In (a), we show an ensemble of decision stumps over three features (211, 22, 22), aggregated piecewise constant functions over feature each (discussed in Section 3) and evaluated under the input randomization ((x)). here a Gaussian. We can compute the independent probability density functions of their outputs (PDFs) (shown in (b)) directly, by evaluating the (Gaussian) cumulative density function (CDF) over the constant regions. Aggregating the individual PDFs (discussed in Section D we can efficiently compute the exact PDF (c) and CDF (d) of the ensemble's ' output. To evaluate and certify the smoothed model, we can now simply look up the median prediction and success probability, respectively, in the CDF, without requiring sampling.
DRS combines f,- norm certificates over numerical features, computed as described above, with an efficient worst-case analysis for fo-perturbations of categorical features in order to, for the first time, provide joint certificates. To train models amenable to certification with DRS, we propose a robust MLE optimality criterion for training individual stumps and two boosting schemes targeting the certified robustness of the whole ensemble. We show empirically that DRS significantly improves on the state-of-the-art, increasing certified accuracies on established benchmarks up 4-fold.
Main Contributions Our key contributions are:
DRS, novel and efficient (De-) (De-)Randmmized Smoothing approach for robustness certifi- cation, enabling joint deterministic certificates over numerical and categorical variables (Section()) 3).
A novel MLE optimality criterion for training decision stumps robust under input random- ization and two boosting approaches for certifiably robust stump ensembles (Section 4
An extensive empirical evaluation, demonstrating the effectivvness of our approach and establishing a new state-of-the-an in a wide range of settings (Section 5).
2 Background on Randomized Smoothing
For given base model F; Rd + [C], classifying inputs to one of C' E -22 classes, Randomized Smoothing (RS) is a method to construct a classifier G: Rd > [C] with robustness guarantees. For a randomization scheme Φ: 2 we define the success probability Py Py:=Pa'roter (F( > = and G(x)): = arg max Py- Depending on the choice of Φi, we obtain different certificates of the form:
Theorem 2.1 (Adapted from Cohen et al. 24
Yang et al. (5)). IFF(F(((z)) = y) = Py 2 Ps
and py > 0.5, then G(x 5) = for all satisfying ||ö1| < R with R == p(Py)-

---

In particular, we present two instantiations that we uti- lize throughout this paper in Table where 4- is the inverse Gaussian CDF. Similar results, yielding other f--norm certificates, can be derived for a wide range of input randomization schemes [25 26). Note that, by using more information than just py c.g., Pe for the ru class c, tighter certificates can be obtained 24 22]. Once Py is computed,
Table 1: Randomized Smoothing guarantees.
((x)
R = ((p))
6 x: Unif[[-A,
2X(py - 2))
l2 x x+ x+1(0,,l)
o$ o& (Pu)
directly calculate the certifiable radius R. := p(py). For broader overview of variants of Randomized Smoothing, please refer Section 6
For most choices of F and Φ. the exact success probability Py can not be computed efficiently. Thus lower bound Py estimated with confidence 1 (typically a 10-3) using Monte Carlo sampling and the Deyman-Pearson lemma (28). Not only is this extremely computationally expensive, as typically 100 000 samples have to be evaluated per data point, but this also severely limits the maximum certifiable radius (see Fig. (6) and only yields probabilistic guarantees. Additionally, if the number of samples is not sufficient for the statistical test, the procedure will abstain from classifying.
In the following, we will show how considering specific class of models F allows to compute the success probability Py exactly, overcoming these drawbacks, and thus invoke p(pg) to compute deterministic certificates over larger radii, orders of magnitude faster than RS.
3
Smoothing for Decision Stump Ensembles
Tree-based models such as decision stump ensembles often combine exceptional performance on tabular data [1] with good interpretability, making them ideal for many real-world high-stakes applications. Here, we propose a (be-)Randomizze Smoothing approach, DRS, to equip them with deterministic robustness guarantees. For this, we first revisit decision stump ensembles and then show that their structure permits an exact evaluation under isotropic input randomization schemes, such as those discussed in Section 2 Finally, we propose joint certification over numerical and categorical variables, as many practical tabular datasets often contain both variable types.
Stump Ensembles We define a decision stump as fz) Nm + (Tr.m "n.m ) 2 Sem, with leaf predictions "I,m, E [0, 1). split position Um. and split variable jm. We construct unweighted ensembles, particularly suitable for Smoothing (29] of M such stumps fMr: IRd + 10, 1] as
M
(M) = Σ fm(()).
and treat them as a binary classifiers 11 (a) While our approach is extensible to multi-class
classification by replacing the scalar leaf predictions y with prediction-vest -eectors,, assigning score per class, we focus on the binary case in this work.
Smoothed Stump Ensemble We now define smoothed stump ensemble gM along the lines of Randomized Smoothing as discussed in Section 2 by evaluating fMr not only on the original input but rather on a whole distribution of x' ((x))
U111
U2
(M x)) := Pa'
(f) (x')
0.5].
In this work, we consider randomization schemes ((x) that are (i) isotropic, i.e., the dimensions of x' d(z) are indepen- dently distributed, and (ii) permit efficient computation of their marginal cumulative distribution functions (CDF). This includes a wide range of distributions, e.g., the Gaussian and Uniform distributions used Table D and others commonly
f1(2.)
7
7r.1
+
+
+
f2(2.)
72
71.2
7/22
used for RS (25). By denoting the model CDF as (2) PP''oo( (f(e') (f(')
F((xs))
36.1
7/122
76.3
z). we can alternatively define zMr as yas (x) : 1 -F M. (0.5), which will become useful later. For a label y E (0. we obtain the success probability Py = byy - F. (0.5) of predicting y
P1
P2
Figure 2: meta-stump constructed from two stumps.
for sample from ((x).
3

---

Algorithm/ Stump Ensemble PDF computation via Dynamic Programming
function COMPUTEPDF (T, o)) V; ()) pdf = 0 for / E [M A 11,
pdf [ =
For 0 stumps all probability mass is
for i = 1 to d do
for j = 1 to M, do
for t = to M A 1 F do
pdf Tzyl = pdf + Tayl + pafli 1][t] Pat-o(=) < x [nyl
return pdf
Meta-Stumps To evaluate Py exactly illustrated in Fig. [ we group the stumps constituting an ensemble by their split variable jm obtain one mela-stump Sú per feature i. The key idea that outputs of these meta-stumps are now independently distributed under isotropic input randomization (illustrated in Fig. (b)), allowing us to aggregate them efficiently later on.
We showcase this in Fig. where two stumps (f1 and f2) are combined into the meta-stump f. Formally, we have
== = Σ fmx), I= {m E [M] fm = =i}, MEI,
define Mi- I and rewrite our ensemble as (x) = M7 Ei= f((;)). Every meta-stump can be represented by its split positions Vi.j, sorted such that Us I 0i and its predictions Th. El=l Yr.t E|E) "M,. on each of the resulting [Z,] + regions, written (7, v);-
CDF Computation Now we leverage the independence of our meta-stumps' output distributions under an isotropic input randomization scheme é to compute the PDF of their ensemble efficiently via dynamic programming (DP) (illustrated in Fig.
F (c) and explained below). Given its PDF, can trivially compute the ensemble's CDF FM, allowing us to evaluate the smoothed model exactly (illustrated in Fig. (d)). This efficient CDF computation constitutes the core of DRS.
In more detail, we observe that the PDF of stump ensemble the convex sum of exponentially many (max, I ()) Dirac-delta distributions. To avoid this exponential blow-up, we discretize all leaf predictions y to grid of A values (typically A 100), when constructing the smoothed model IM. For each Yi.j we define a corresponding le. E {O....,
"e....,MA. M; A} such that %, = Fig, Now,
A
[[[ [t] corresponds to the weight of the Dirac-delta AM after considering the first i meta-stumps (in any arbitrary but fixed order). We show the PDF computation in Algorithm and provide intuition below. We initialize [df[0][+] by allocating all probability mass to = 0 (pd [0]=1.. Now, we compute pdf [i] 1] [+] from pd [i-] [+] by accounting for the effect of the 7th meta-stump follows: The weight of the Dirac-delta at t after considering i meta-stumps is exactly the sum over the weights of the Dirac-deltas t-I's, after i-1 meta-stumps, weighted with the probability Pt, == Pz)->((=]]))) [V x S vxy]
construct DP-table, where every entry pdf
associated with an output of f
of the 1th meta stump predicting Fi.j. We compute Ps.j as the probability of the randomized z! lying between Ua and vújj (padded with oo and do the left and right, respectively).
illustrated in Fig. 2 After termination, the last line of the DP-table pdf [+] contains the full PDF (see Fig. [()). Formally we summarize this in the theorem below, delaying formal proof to App. App.A.I] A.
Theorem 3.1. For 2 E [0, 1]. (M) = Σ - [=MA] ptf[d[tt] describes the exact CDF and thus success probability Py = P (f
(0.5) E 10.1).
Note that the presented algorithm is slightly simplified, and actually only have track the range of non-zero entries of one row of the DP-table. This allows us to compute the full PDF and thus certificates for smoothed stump ensembles very efficiently, e.g., taking only around 1.2 s total for the MNIST 2 vs. 6 task (around 2.000 data points and over 500 stumps).
Certification Recall from Section 2 that, given the success probability Py. robustness certification for l norm bounded perturbations reduces to computing the maximal certifiable robustness radius R = p(p,)). . For all popular fy no-nosss, p (and its inverse p-1; used shortly) can be either evaluated symbolically [24]] 25 precomputed efficiently [30] 31), such that the core challenge of certification

---

becomes computing (a lower bound to) Py. which we solve efficiently via Theorem 3.1 Alternatively, for a given target radius r, we need to check whether Py 2 p (r) by equivalently calculating
1 - (r) if y = (r)
(M. = =FM M, (z)
(3)
if = 0
and checking (M) > 0.5. This corresponds to asserting that class is predicted at least 2 of the time. Here, the inverse CDF (2) can be efficiently evaluated using the step-wise FM,. computed via Theorem 3.1 We will see in Section 4 that this view useful when training stump ensembles for certifiabilityy. Finally, we want highlight that this approach can be used with all common randomization schemes yielding certificates for different ly-norm bounded adversaries.
Categorical Variables & Joint Certificates For practical applications, it is essential to handle both numerical and categorical features jointly. To consider a categorical feature I; E {l.....dd .d. } in our stump ensemble, we construct a di-ary stump f:: [d.] >> [0. 1] returning a value "H. corresponding meta-stump with M, for normalization.
to each of the d, categorical values and treated
To provide certificates in this setting, we propose a novel scheme combining an arbitrary 4--norm certificate of radius Tp over all numerical features, computed discussed above, with an to certificate of radius ry over all categorical features C, computed using an approach adapted from Wang et al. [23]. Conceptually, compute the worst-case effect of every individual categorical variable independently, greedily aggregate these worst-case effects, and account for them in our ensemble's s CDF.
Given a meta- meta-stump's stump's 's prediction on concrete sample qi f(;;;) as well as its maximal and minimal output and 4, respectively, we compute the maximum and minimum perturbation effect to 5; M and 2 " respectively. Given the set of categorical features C, we can compute the worst-case effect when perturbing at most ro samples as
8.p = max Σ 0i R
8.L. S RCC
ER
by greedily picking the ro largest 5, For &r. we proceed anal- ogously. Shifting the CDF, computed above, by 8 and á for samples with labels 0 and y = 1, respectively, before com- puting the success probability Py. allows us account for the worst-case categorical perturbations exactly. We illustrate this for a sample with y = 0 in Fig. 3 where we show the CDFs obtained by all possible perturbations of at most to categorical variables, bounded to the right by those obtained by shifting the original by 5,. Note that here no smoothing over the categorical variables is done or required, making inference trivial.
Fux
1.0-
2
in 0
0.5
0,0
0.3
0.5
0.7
Figure 3: CDF shifted by the effect of categorical feature perturbations.
4 Training for and with (De-JRandomized Smoothing
To obtain large certified radii via smoothing, the base model has to be robust to the chosen randomiza- tion scheme. To train robust decision stump ensembles, we propose robust MLE optimality criterion for individual stumps (Section 4.1) and two boosting schemes for whole ensembles (Section 4.2
4.1 Independently MLE-Optimal Stumps
To train individual stump (x) NM + (fr.m - "m ) Le,,,, Sum its split feature ims split position Ums and leaf predictions "I,,, Tr.m have to be determined. We choose them in an MLE- optimal fashion with respect to the randomization scheme starting with Uma follows: We consider the probabilities pr,; (vm) = P Par~o(a)))) | I Um]] and Pr, = 1 pt.i(Um of x lying to the left or the right of Um. respectively, under the input randomization scheme Φ. To avoid clutter, we drop the explicit dependence on Um in the following. For an i.i.d. dataset with n samples (æ,, yi) (:)== (2' ))), define the probabilities P" Σ (xlp:=y) Pj. of picking the j r1, leaf, conditioned on the
target label, and P; = p9 + p/ as their sum to compute the entropy impurity Hannopy
332 as
P" Pj
H Hemnopy =
Σ P
Σ
log
Pj
JE(l.r)
(E
5

---

We then choose the Um approximately minimizing H Hemropy via line-search. After fixing Um this way. we compute the MLE-optimal leaf predictions ?) 3MLE and 7r 7.L as:
AMLE
MLE.
arg max P ()()), arg max 7..7-
E. Ee (((r)) Dog Plys: x',, fm]]
71
7r
arg max 7.r
Σ
Pl, log(11111 7)) + Pr, log(1 - 7+)
()(
Σ
PL, log(?)) Pr, log()))())))
arg max pi lo - 7) + p. log(1 - 7+) + pł log(n)) + p, log(?));
where the second line obtained by splitting the sum over samples by class and explicitly computing the expectation. We solve the maximization problem by setting the first derivatives ह. and our optimization objective to zero and checking its Hessian to confirm that
3%. of
dMLE
Pi
AALE
D
0 Pi
Pt
P + PC
O.MLE and Um are even jointly MLE-optimal, when Um is chosen as the exact instead of approximate minimizer of the entropy impurity.
are indeed maxima. We show App. A.2 that 7
3.MEE
Ensembling To train an ensemble of independently MLE-optimal decision stumps, we sequentially train one stump for every feature jm [d] and construct ensemble with equal weights, rejecting stumps with an entropy impurity Hentrop above a predetermined threshold.
4.2 Boosting Stump Ensembles for Certifiable Robustness
Decision stumps trained this way maximize the expected likelihood under the chosen randomization scheme. As- suming (due the law of large numbers) Gaussian out- put distribution, this corresponds to optimizing for the median output, which determines the clean prediction. However, certified correctness at a given radius r is deter-
Cleam Prodiction
cluss
mined by the prediction y((x,r) r) = -, (z(r)) at the z(r) = ly - م (r) percentile of the output distribution. Where we call y' the certifiable prediction, as certification is now equivalent to checking y = 1 1y(a)))>0.5 (Eq. (3).
0.5-
class
Cest. Prodiction 1t rig 0.9)
This difference is illustrated prediction is correct (class 1) while the certifiable predic- tion is incorrect. To align our training objective better with certified accuracy, we propose two novel boosting schemes along the lines of the popular TREEBOOST B3
Fig. [] where the clean
0.0
0.5
1.
Figure 4: Inverse CDF F=1
and ADABOOST (34]
Gradient Boosting for Certifiable Robustness The key idea of gradient boosting is to compute the gradient of loss function with respect to an ensemble's outputs and then add a model to the ensemble that makes prediction along this gradient direction. Implementing this idea, we adapt TREEBOOST [33 to propose GOBTREEBOOST At a high level, we add stumps to the ensemble, which aim to predict the residual between the target label and the current certifiable prediction. Concretely, to add the mh stump to our ensemble, we begin by computing the current ensemble's 'e'es certifiable predictions y (r)) at target radius r and then defining the pseudo labels y y y as the residual between the target labels y and the certifiable predictions y((r). This yields a regression problem, which we tackle by choosing feature jn and split threshold um (approximately) minimizing MSE impurity under input randomization before computing 7M. and Tr.m as approximate minimizers of the cross-entropy loss over the whole ensemble. Please see App. A.3 for a more detailed discussion of ROBTREEBOOST.

---

Table 2: Natural accuracy (NAC) [%] and certified accuracy (CA) [%] with respect to 4 and fo-n bounded perturbations. Results for Wang et al. [23] as reported by them. Larger is better.
Standard Training
Wang al. 23
Ours (Independent)
Ours (Boosting)
Perturbation
Dataset
Radius
NAC
NAC
CA
NAC
CA
NAC
CA
BREASTCANCER
1.0
99.3
98.5
64.2
100.0
81.0
100.0
83.9
74.7
69.5
77.9
72.1
4 morm
FMNIST SHOES
0.5
95.0
87.6
67.8
85.8
83.3
87.2
84.2
MNIST
99.1
95.5
99.3
98.1
MNIST 2 VS.
1,0
96.0
92.3
66.5
96.3
93.9
96.6
94.1
BREASTCANCER
0.7
99.3
91.2
60.6
100.0
75.2
100.0
82.5
DIABETES
0.05
74.7
68.2
79.9
71.4
FMNIST SHOES
0.4
95.0
75.5
$1.5
86.8
81.2
91.0
84.5
MNIST
99.1
95.6
99.2
96.3
MNIST 2 VS. 6
0.8
96.0
86.3
23.0
96.3
89.6
96.3
89.6
Adaptive Boosting for Certifiable Robustness The key idea of adaptive boosting is build an ensemble by iteratively training models, weighted based on their error rate, while adapting sample weights based on whether they are classified correctly. We build on ADABOOST [34] to propose KOBADABOOST We construct an ensemble of K stump ensembles via hard voting, where every ensemble is weighted based on its certifiable accuracy. To train a new ensemble, we increase the weights of all samples that are currently not classified certifiably correctly at given radius r. We choose stump ensembles instead of individual stumps as base classifiers because single stumps often can not reach the success probabilities under input randomization required for certification. To compute the certifiable radius for such an ensemble FK. we compute the certifiable radii R²* of the individual stump ensembles JMr sort them in decreasing order such that R > R*+ and obtain the largest radius R* such that the weights of the first ht ensembles sum up to more than half of the total weights. Please see App. A.4 for a more detailed discussion of ROBADABOOST.
5 Experimental Evaluation
In this section, we empirically demonstrate the effectiveness of DRS in a wide range of settings. We show that DRS significantly outperforms the current state-of-the-art for certifying tree-based models on established benchmarks, using only numerical features [Section[..] before highlighting its novel ability to obtain joint certificates on set of new benchmarks (Section 5.2). Finally, we perform an ablation study, investigating the effect of DRS's key components (Section 5.3)
We implement our approach in Py'Torch (35 and evaluate it on Intel Xeon Gold 6242 CPUs and an NVIDIA RTX 2080Ti. We compare to prior work on the DIABETES 36..
Experimental Setup
BREASTCANCER (37], FMNIST-SHOFS (38) MNIST 1 vs. (39], and MNIST vs. 6 39 datasets and are the first to provide joint certificates of categorical and numerical features, demonstrated on the ADULT (37] and CREDIT [37] datasets. For more detailed description of the
experimental setup, please refer to App. B
5.1
Certification for Numerical Features
In Table 2 compare the certified accuracies obtained via DRS ensembles of independently MLE optimal stumps (Independent) or boosted stump ensembles (Boosting) to the current state-of- the-art, Wang et al.
233 and standard training 40) using established benchmarks 23).
Independently MILE Optimal Stumps We first consider stump ensembles trained without boosting as described in Section 4.1 and observe that DRS obtains higher certified accuracies in all settings and higher natural accuracies in most. For example, on MNIST 2 vs. 6, we increase the certified accuracy at an & radius of r2 = 0.8 from 23.0% to 89.6%, almost quadrupling it compared to Wang et al. 23 while also improving natural accuracy from 86.3% to 96.3%.
Boosting for Certified Accuracy Leveraging the boosting techniques introduced in Section 4.2 ROBTREEBOOST for BREASTCANCER and DIABETES and ROBADABOOST for FMNIST-SHOFE MNIST 1 vs. 5, and MNIST 2 vs. 6, we increase certifiable and natural accuracies even further in most settings. For example, compared to our independently trained stump ensemble, we improve the certified accuracy for MNIST I vs. 5 at an & f-radius of r = 1.0 from 94.1% % to 98.1 % and for BREASTCANCER an E--ruu of r2 0.7 from 75.2% to 82.5%.

---

Table Balanced certified accuracy (BCA) [%] under joint eu- and & pe-perturbations of categorical and numerical features, respectively, depending whether model uses categorical and/or numerical features. The balanced natural accuracy the BCA at radius r = 0.0. Larger better.
Categorical Features
BCA without
with Numerical Features &a Radius
Dataset
to Radius no
Numerical Features
0.00
0.25
0.50
0.75
1.00
1.25
1.50
nO
74.9
65.7
42.4
27.4
14.5
8.9
5.1
0
76,6
77.5
73.9
68.1
63.3
48.7
40.7
35.2
ADULT
1
$7.4
66.0
61.7
$3.9
47.4
34.3
26.6
21.8
yes
2
33.5
51.4
46.2
37.5
29.3
21.5
17.1
13.4
3
36.7
24.1
15.4
10.3
5.7
no
56.1
44.5
33.3
17.7
9.7
7:2
5.0
0
70.7
74.1
70.3
67.3
59.7
57.1
$4.9
53.4
CREDIT
1
48.2
$2.7
47.7
41.7
38.3
37.1
35.1
34.7
yes
2
26.4
29.3
26.0
23,8
19.2
16.8
13.5
13.0
3
13.6
5.2 Joint Certificates for Categorical and Numerical Features
In Table 3 we compare models using only numerical, only categorical, or both types of features with regards their balanced certified accuracy (BCA) (accounting for class frequency) at different combinations of lg- and fo-radii for numerical and categorical features, respec- tively. We observe that models using both categorical and numerical features perform notably better on clean data, highlighting the importance of utilizing and thus also certifying them combination. Moreover, categori- cal features make the model significantly more robust to l2 perturbations, e.g., at 22-radi 2 0.75, they improve certified accuracies, even when 2 categorical features (of only and 7 for ADULT and CREDIT, respectively) adversarially perturbed. We visualize this in Fig. showing BCA over & perttururbttion radius and confirm that the model utilizing only numerical features (dotted line) loses accuracy much quicker with perturbation magnitude than the model leveraging categorical variables (solid lines). As are the first to tackle this setting, we do not compare to other methods but provide more detailed experiments in App. C.I
Balanced Certified Accurscy [%]
100
1o
75
1o0 eateguetial Socturee
50
25
0.0
0.5
1.0
1.5
2.0
Eg Radius T2
Figure 5: Effect of fu-perturbations on fx- robustness for CREDIT.
5.3 Ablation Study
We first illustrate the effectiveness of our derandomization approach, before demonstrating the benefit of training with our MI_E optimality criterion and investigating the effect of the noise level on DRS.
(De-)Randomize) vs Randomized Smoothing In Fig. 6 we compare DRS, (dotted line) and sampling-based RS (solid lines), w.r.t. certified accuracy over & radii. We observe that the sampling-basee
Certified Accuracy
[%]]
100-
1.00
estimation of the success probability in RS significantly limits the obtained certifi- able radii. While this effect is particularly pronounced for small sample counts n, increasing the maximum certifiable radius, visible as the sudden drop in certifiable accuracy, requires exponentially increasing number of samples, making the certification large radii intractable. DRS, in contrast, can compute exact success probabilities and thus deterministic guarantees for much larger radii, yielding a 33.1% increase ACR compared using 100 000 samples. Additionally, DRS is multiple orders of magnitude faster than RS, here, only requiring approximately 6.45 10 s per sample. For more extensive experiments, please refer to App. C.2
75-
1:0000
50
1388 (muzs
25
E Radius
Figure 6: DRS vs. RS with various sample counts MNIST vs. 5.

---

MLE Optimality Criterion In Table we eval- uate our robust MLE optimality criterion (MLE) by comparing it to the standard entropy criterion applied to samples drawn from the input randomiza- tion scheme (Sampling) or the clean data (Default). We observe that the ensemble trained on the clean data (Default) suffers from mode collapse when evaluated under noise. In contrast, both approaches considering the imput randomization perform much better, with our robust MLE approach outperform- ing sampling by significant margin, especially at large radii. For more extensive experiments, please refer App.
Table 4: Comparison of training with the exact distribution (MLE), randomly perturbed data (Sampling), clean data (Default) on BREAST- CANCER for o 1.
Certified Accuracy [X] Radius
Method
ACR
0.0
0.25
0.5
0.75
MLE (Ours)
0.675
100.0
97.1
86.1
30.7
Sampling
0.567
99.3
95.6
75.2
Default
0.356
26.3
25.5
25.5
25.5
Effect of Noise Level In Fig. 7 we compare the certified accuracy over frrrdii for range of dif- ferent noise magnitudes and ensembles of inde- pendently MLE optimal stumps. We observe that at large perturbation magnitudes, we obtain stumps that 'think outside the (hyper-)box) i..., choose splits outside the original data range, making their ensembles exceptionally robust, even at large radii. In particular, we obtain a certifiable accuracy of 87.3% at radius F1 4.0, while the state-of- the-art achieves only 83.8% at r1 = 1.0 [23]. We provide more experiments for varying noise magni- tudes in App. C.4
Certified Accuracy [%]
100
- 0.5
A 1.0
75-
= 2.0
50-
16.0
25
0-
0.0
4.0
8.0
12.0
16.0
& Radiuu Ti
Figure 7: Comparing DRS for various noise levels on MNIST 1 vs. 5.
6 Related Work
(De-)Randomizer Smoothing Probabilistic certification methods 41
42 24 are popular approach 43 46 threat models 225 30
for obtaining robustness certificates for a wide range of tasks [31
31 43 53), and
trade-offs [54]. These methods follow the general blueprint
discussed Section and consider arbitrary base classifiers, though specially trained (55 While recent work [29 58 has found ensembles to be particularly suitable base classifiers, they use neural networks and can thus, in contrast to our work, not leverage their structure. Specifically designed randomization schemes [5] [33 enable efficient enumeration and thus deterministic certificate for, contrast to these approaches, we permit arbitrary isotropic continuous randomization schemes, allowing to leverage comprehensive results RS to obtain robustness guarantees against a wide range of f--norm bounded adversaries [55]
c.g., patch attacks or & fn-orrm perturbations.
Certification and Training of Free-Based Models In the setting of lo robustness, where every feature can be perturbed independently, various methods have been proposed train 4 22
59 61
and certify [22 62-644 robust decision trees and stumps. However, fx robust models are still vulnerable to other l, norm perturbations [65 (6), which cover many realistic perturbations better
and are the focus of this work. There, the admissible perturbation of one feature depends on the perturbations of all others, making the above approaches leveraging their independence not applicable.
On the other hand, Kantchelian et al. (67] discuss complete robustness certification of tree ensembles in the f,-norm setting via MILP. However, this approach intractable in most settings due its Co- NP-complete complexity. Wang et al. (23 propose an efficient but incomplete DP-based certification algorithm for stump ensembles based on ever-approximatin the maximum perturbation effect in the f--norm setting. While similarly fast as our approach, we show empirically in Section 3 that DRS obtains significantly stronger certificates. Wang et al. [3] further introduce an incomplete certification algorithm for tree ensembles, which is based on computing the distance between the pre-image all trees' leaves and the original sample. As they report significantly worse results using this approach than with stump ensembles, we omit a detailed comparison.

---

Limitations and Societal Impact
Limitations While able handle arbitrary stump ensembles, and being extensible arbitrary decision trees (see App.D) DRS can not handle arbitrary ensembles of decision trees. However, as these have been shown be significantly more sensitive f--norm perturbations than stump ensembles (23,, we believe this limitation to be of little practical relevance. Further, like all Smoothing- based approaches, we construct smoothed model from a base classifier and only obtain robustness guarantees for the former. In contrast to standard Randomized Smoothing approaches, we can, however, evaluate the smoothed model exactly and efficiently.
Societal Impact As our contributions improve certified accuracy and certification radii while retaining high natural accuracy, they could help make real-world Al systems more robust and thus generally amplify both any positive or negative societal effects. Further, while we achieve state-of- ofte-of-the-art results, these may not be sufficient to guarantee robustness real-worke deployment and could give practitioners a false sense of security, leading to them relying more on our models than is justified.
8 Conclusion
We propose DRS, a (De-)Randomized Smoothing approach to robustness certification, enabling joint deterministic certificates over numerical and categorical variables for decision stump ensembles by leveraging their structure to compute their exact output distributions for a given input randomization scheme. The key insight enabling this is that this output distribution can be efficiently computed by aggregating independent distributions associated with the individual features used by the ensemble. We additionally propose robust MLE optimality criterion for training individual decision stumps and two boosting schemes improving an ensemble's certifiable accuracy. Empirically, we demonstrate that DRS significantly outperforms the state-of-the-art for ree-based models in wide range of settings, obtaining up to 4-fold improvements in certifiable accuracy.
10

---

References
[1] R. Shwartz-Ziv and A. Armon, "Tabular data: Deep learning is not all you need," Information Fusion, vol. 81, 2022.
[2] B. Biggio, I. Corona, D. Maiorca, B. Nelson, N. Srndic, P. Laskov, G. Giacinto, and F. Roli, "Evasion attacks against machine learning at test time," in Machine Learning and Knowledge Discovery in Databases European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part III, vol. 8190, 2013.
[3] C. Szegedy, W. Zaremba, I. Sutskever, Bruna, D. Erhan, I. J. Goodfellow, and Fergus, "Intriguing properties of neural networks," in Proc. of ICLR, 2014.
[4] H. Chen, H. Zhang, D. S. Boning, and C. Hsieh, "Robust decision trees against adversarial examples," in Proc. of ICMI,, vol. 97, 2019.
[5] F. Cartella, O. Anunciação, Y. Funabiki, D. Yamaguchi, T. Akishita, and O. Elshocht, "Ad- versarial attacks for tabular data: Application to fraud detection and imbalanced data," in Proceedings of the Workshop on Artificial Intelligence Safety 2021 (SafeAI 2021) co-located with the Thirty-Fifh AAAI Conference on Artificial Intelligence (AAAI 2021), Virtual, February 8, 2021, vol. 2808, 2021.
[6] Y. Mathov, E. Levy, Z. Katzir, A. Shabtai, and Y. Elovici, "Not all datasets are born equal: On heterogeneous tabular data and adversarial examples," Knowl. Based Syst., vol. 242, 2022.
[7] G. Singh, T. Gehr, M. Püschel, and M. T. Vechev, "An abstract domain for certifying neural networks," " Proc. ACM Program. Lang,, vol. 3, no. POPL, 2019.
[8] K. Xu, Z. Shi. H. Zhang. Y. Wang. K. Chang, M. Huang, B. Kailkhura, X. Lin, and C. Hsich, "Automatic perturbation analysis for scalable certified robustness and beyond," in Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 12, 2020, virtual, 2020.
[9] T. Gehr, M. Mirman, D. Drachsler- Cohen, P. Tsankov, S. Chaudhuri, and M. T. Vechev, "A12: safety and robustness certification of neural networks with abstract interpretation." in 2018 IEEE Symposium on Security and Privacy, SP 2018, Proceedings, 21-23 May 2018, San Francisco, California, USA, 2018
[10] S. Wang. K. Pei, J. Whitehouse, J. Yang, and S. Jana, "Efficient formal safety analysis of neural networks," " in Advances in Neural Information Processing Systems 31; Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, 2018
[11] T. Weng. H. Zhang, H. Chen. Song, C. Hsich, L. Daniel, D. S. Boning, and S. Dhillon. "Towards fast computation of certified robustness for relu networks," in Proc. of ICML, vol. 80, 2018.
[12] E. Wong and J. Z. Kolter, "Provable defenses against adversarial examples via the convex outer adversarial polytope," in Proc. of ICML, vol. 80, 2018.
[13] G. Singh, T. Gehr, M. Mirman, M. Püschel, and M. T. Vechev, "Fast and effective robustness certification," in Advances in Neural Information Processing Systems 31: Anmual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, 2018
[14] M. N. Müller, G. Makarchuk, G. Singh, M. Plischel, and M. T. Vechev, "PRIMA: general and precise neural network certification via scalable convex hull approximations." Proc. ACM Program. Lang., vol. 6, no. POPI., 2022.
[15) V. Tjeng, K. Y. Xiao, and R. Tedrake, "Evaluating robustness of neural networks with mixed integer programming." in Proc. of ICLR, 2019.

---

[16] S. Dathathri, K. Dvijotham, A. Kurakin, A. Raghunathan, J. Uesato, R. Bunel, S. Shankar, J. Steinhardt, J. Goodfellow, P. Liang, and Kohli, "Enabling certification of verification- agnostic networks via memory-efficiett semidefinite programming." in Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 12, 2020, virtual, 2020.
[17] R. Ehlers, "Formal verification of piece-wise linear feed-forwart neural networks," in Automated Technology for Verification and Analysis 15th International Symposium, ATVA 2017, Pune, India, October 3-6, 2017. Proceedings. vol. 10482, 2017.
[18] M. Mirman, T. Gehr, and M. T. Vechev, "Differentiable abstract interpretation for provably robust neural networks," in Proc. of ICML, vol. 80, 2018.
[19] M. Balunovic and M. T. Vechev, "Adversarial training and provable defenses: Bridging the gap." in Proc. of ICLR, 2020.
[20] A. Raghunathan, J. Steinhardt, and P. Liang, "Certified defenses against adversarial examples." in Pruc. of ICLR, 2018.
[21] S. Gowal, K. Dvijotham, R. Stanforth, R. Bunel, C. Qin, J. Uesato, R. Arandjelovic. T. A. Mann, and P. Kohli, "On the effectiveness of interval bound propagation for training verifiably robust models," ArXiv preprint, vol. 1810.1211,,, 2018.
[22] M. Andriushchenko and M. Hein, "Provably robust boosted decision stumps and trees against adversarial attacks," in Advances in Neural Information Processing Systems 32: Annual Confer- ence on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, 2019.
[23] Y. Wang, H. Zhang, H. Chen, D. S. Boning, and C. Hsieh, "On Ip Ip-norm robustness of ensemble decision stumps and trees," in Proc. of ICML, vol. 119, 2020.
[24] M. Cohen, E. Rosenfeld, and J. Z. Kolter, "Certified adversarial robustness via randomized smoothing," in Proc. of ICML, vol. 97, 2019.
[25] G. Yang, T. Duan, J. E. Hu, H. Salman, I. P. Razenshteyn, and J. Li, "Randomized smoothing of all shapes and sizes," " in Proc. of ICML, vol. 119, 2020.
[26] D. Zhang, M. Ye, C. Gong, Z. Zhu, and Q. Liu, "Black-box certification with randomized smoothing: A functional optimization based framework," in Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[27] K. D. Dvijotham, J. Hayes, B. Balle, Z. Kolter, C. Qin, A. György, K. Xiao, S. Gowal, and P. Kohli, "A framework for robustness certification of smoothed classifiers using f-divergences," in Proc. of ICLR, 2020.
[28] Neyman and F. S. Pearson, "Ix. on the problem of the most efficient tests of statistical hypotheses,"" Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, vol. 231, no. 694-706, 1933.
[29] M. Z. Horváth, M. N. Müller, M. Fischer, and M. T. Vechev, "Boosting randomized smoothing with variance reduced classifiers," in Proc. of ICLR, 2022.
[30] G. Lee, Y. Yuan, S. Chang, and T. S. Jaakkola, "Tight certificates of adversarial robustness for randomly smoothed classifiers," in Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, 2019.
[31] A. Bojchevski, J. Klicpera, and S. Günnemann, "Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more," " in Proc. of ICML, vol. 119, 2020.
[32] B. Bustos, D. A. Keim, D. Saupe, T. Schreck, and D. V. Vranic, "Using entropy impurity for improved 3d object similarity search," " in Proceedings of the 2004 IEEE International Conference Multimedia and Expo, ICME 2004, 27-30 June 2004, Taipei, Taiwan, 2004.
12

---

[33] J. H. Friedman, "Greedy function approximation: gradient boosting machine," Annals of statistics, 2001.
[34] Y. Freund and R. E. Schapire, "A decision-theoretic generalization of on-line learning and an application to boosting," J. Comput, Syst. Sci., vol. 55, no. 1, 1997.
[35] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Köpf, E. Yang. Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L.. Fang, J. Bai, and S. Chintala, "Pytorch: An imperative style, high-performance deep learning library," in Advances in Neural Information Processing Sys- tems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8- 14. 2019, Vancouver, BC, Canada, 2019.
[36] J. W. Smith, E. Everhart, W. C. Dickson, W. C. Knowler, and R. S. Johannes, "Using the adap learning algorithm to forecast the onset of diabetes mellitus," " in Annual Symposium on Computer Application in Medical Care, 1988.
[37] D. Dua and C. Graff, "UCI machine learning repository," 2017.
[38] H. X. an. "Fashion- mmist:: novel image dataset for benchmarking machine learnin," ArXiv preprint, vol. abs/ 708.07747, 2017.
[39] Y. LeCun and C. Cortes, "MNIST handwritten digit database," " 1998.
[40] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhoferr R. Weiss, V. Dubourg. J. VanderPlas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay, "Scikit-learn: Machine learning in python," " CoRR, vol. abs/1201.044 1.0.0.04,,,0. 2012. [Online]. Available: http://arkiiorrr//bb///111..1
[41] B. Li, C. Chen, W. Wang, and L. Carin, "Certified adversarial robustness with additive noise," in Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, 2019.
[42] M. Lécuyer, V. Atlidkkis, R. Geambasu, D. Hsu, and S. Jana, "Certified robustness to adversarial examples with differential privacy," in 2019 IEEE Symposium on Security and Privacy, SP 2019, San Francisco, CA, USA, May 19-23, 2019, 2019.
[43] Z. Gao, R. Hu, and Y. Gong, "Certified robustness of graph classification against topology attack with randomized smoothing," " in IEEE Global Communications Conference, GLOBECOM 2020, Virtual Event, Taiwan, December 7-11, 2020, 2020.
[44] P. Chiang, M. J. Curry, A. Abdelkader, A. Kumar, J. Dickerson, and T. Goldstein, "Detection as regression: Certified object detection with median smoothing," in Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[45] M. Fischer, M. Baader, and M. T. Vechev, "Scalable certified segmentation via randomized smoothing," in Proc. of ICML, vol. 139, 2021.
[46] J. Jia, X. Cao, B. Wang, and N. Z. Gong, "Certified robustness for top-k predictions against adversarial perturbations via randomized smoothing," in Proc. of ICLR, 2020.
[47] M. Fischer, M. Baader, and M. T. Vechev, "Certified defense to image transformations via randomized smoothing." " in Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[48] I. Li, M. Weber, X. Xu, Rimanic, B. Kailkhura, T. Xie, C. Zhang, and B. Li, "Tss: Transformation-specffe smoothing for robustness certification," in ACM CCS, 2021.
[49] B. Wang. J. Jia, X. Cao, and N. Z. Gong, "Certified robustness of graph neural networks against adversarial structural perturbation," " in KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021, 2021.
13

---

[50] J. Schuchardt, A. Bojchevski. J. Klicpera, and S. Günnemann, "Collective robustness certificates," in International Conference on Learning Representations, 2021.
[51] A. Levine and S. Feizi, "Robustness certificates for sparse adversarial attacks by randomized ablation," in The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirly-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, FAAl 2020, New York, NY, USA, February 7-12, 2020, 2020.
[52]
"(de)randomized smoothing for certifiable defense against patch attacks," in Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[53]
"Improved, deterministic smoothing for || certified robustness," in Proc. of ICML, vol. 139, 2021.
[54] M. Z. Horváth, M. N. Müller, M. Fischer, and M. Vechev, "Robust and accurate compositional architectures for randomized smoothing," in ICLR 2022 Workshop on Socially Responsible Machine Learning, 2022.
[55] Jeong and J. Shin, "Consistency regularization for certified robustness of smoothed classifiers," " in Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[56] R. Zhai, C. Dan, D. He, H. Zhang, B. Gong, P. Ravikumar, C. Hsieh, and L. Wang, "MACER: attack-free and scalable robust training via maximizing certified radius," in Proc. of ICLR, 2020.
[57] H. Salman, J. Li, P. Razenshteyn, P. Zhang, H. Zhang, S. Bubeck, and G. Yang. "Provably robust deep learning via adversarially trained smoothed classifiers," in Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8- 8-14, 2019, Vancouver, BC, Canada, 2019.
[58] Z. Yang, L. Li, X. Xu, B. Kailkhura, T. Xie, and B. Li, "On the certified robustness for ensemble models and beyond," in The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022, 2022.
[59] S. Calzavara, C. Lucchese, G. Tolomei, S. A. Abebe, and S. Orlando, "Treant: training evasion- aware decision trees," Data Min. Knowl. Discov,, vol. 34, no. 5, 2020.
[60] D. Vos and S. Verwer, "Efficient training of robust decision trees against adversarial examples." in Proc. of ICML, vol. 139, 2021.
[61] J.-Q. Guo, M.-Z. Teng, W. Gao, and Z.-H. Zhou, "Fast provably robust decision trees and boosting." " in Proceedings of the 39th International Conference on Machine Learning, 2022.
[62] H. Chen, H. Zhang, S. Si, Li, D. S. Boning, and C. Hsieh, "Robustness verification of tree-based models." in Advances in Neural Information Processing Systems 32: Annual Confer- ence on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, 2019.
[63] F. Ranzato and M. Zanella, "Abstract interpretation of decision tree ensemble classifiers." in The Thirty-Fourthh AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-2, 2020, 2020.
[64] J. Tömbloo and S. Nadjm-Tehrani, "An abstraction-refinmmnnt approach to formal verification of tree ensembles." " in Computer Safety, Reliability, and Security SAFECOMP 2019 Work- shops, ASSURE, DFCSoS, SASSUR, STRIVE, and WAISE, Turku, Finland, September 10, 2019, Proceedings, vol. 11699, 2019.
[65] I.. Schott, J. Rauber, M. Bethge, and W. Brendel, "Towards the first adversarially robust neural network model on MNIST," in Proc. of ICLR, 2019.
14

---

[66] F. Tramèr and D. Boneh, "Adversarial training and robustness for multiple perturbations." in Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8- 14, 2019, Vancouver, BC, Canada, 2019.
[67] A. Kantchelian, J. D. Tygar, and A. D. Joseph, "Evasion and hardening of tree ensemble classifiers, in Proc. of ICML, vol. 48, 2016.
15

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] We substantiate all claims theoretically (Section 3 and
Section 4 empirically (Section 5 appropriate.
(b) Did you describe the limitations of your work? [Yes] We describe the limitations in
Section 7
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We discuss societal impacts in Section
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 3 Section and App.[A]
(b) Did you include complete proofs of theoretical results? [Yes] See Section Section and App.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] We will include them as supplemental material and will release them to the public upon publication. All datasets use are publicly available.
(b) Did you specify all the training details (e.g.. data splits, byperparameters, how they were chosen)? [Yes] We provide full training details in App.
(c) Did you report error bars (c.g., with respect the random seed after running periments multiple times)? [Yes] Both our training and certification methods are deterministic (up to floating point errors), thus main experiments do not contain error bars. However, in App.[C we report numerous error bars with respect to the data split via 5-fold pross-validation.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We provide resource type details in Section and timing details App.
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "zvP6hxjtmV", "reviewer": "Reviewer_K1dy", "summary": "This work tries to produce robust decision stump ensembles against feature perturbation. To achieve this, the authors propose DeRandomized Smoothing (DRS), which can help provide a robust certificate. Moreover, the authors propose a robust MLE optimality criterion for individual stumps and two boosting schemes for whole ensembles. The experimental results look promising and demonstrate the effectiveness of the proposed method.", "questions": "1. Since you already have the code and the pipeline, do you mind comparing the baseline [23] and your proposed method on more tabular data during the rebuttal? Can you produce a table similar to Table 2 for datasets \"mammo\", \"mushroom\", \"bank marketing\", and \"spambase\"?\n\n2. How did you do the train-test set split? Have you performed 5-fold cross validation? Could you conduct 5-CV on Table 2 and report the mean and standard deviation of both the baseline [23] and your proposed method? ", "limitations": "The authors have addressed the limitations in Section 7.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. The writing and figure presentation are very good.\n2. The PDF computation via dynamic programming looks novel.\n3. There are substantial improvements on experimental results, and the code is attached as part of the submission.\n\nWeakness:\n\n1. One part I would like to see better is I wish the authors could conduct experiments comparing the baseline [23] and the proposed work on more tabular data. Breastcancer and Diabetes seem not sufficient to me in Table 2. Moreover, results for the baseline [23] are directly copied from [23]. I would like to see more experimental results on more datasets to assess the effectiveness of the proposed method.\n\n2. The other thing I'm concerned about is that all results reported in Table 2 have no standard deviations. It is not clear for me how the training and test set split was done or whether there is any overfitting.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "vKubyIhxnlH", "reviewer": "Reviewer_7Kxj", "summary": "The paper focuses on the problem of certifying ensembles of decision stumps efficiently and deterministically. By leveraging discretization and piecewise-constant nature of decision stumps, the paper presents a way to compute the output distribution (PDF and CDF) efficiently in a closed form for standard input randomizations without requiring any sampling. This paper also discusses the joint certification over numerical and categorical features and demonstrates how the proposed scheme can be extended to handle categorical features. Consequently, using the deterministic certification scheme, the paper proposes a novel way to construct robust decision tree stumps that can then be used to build ensembles through bagging or gradient boosting and adaptive boosting. The empirical evaluations demonstrate the improved robust predictive performance of the proposed schemes over existing baselines and the ability of the proposed schemes to provide joint certificates. \n", "questions": "- One question is if the authors can provide some intuition behind the dynamic programming based update in Algorithm 1. For example, why would the update of $\\text{\\tt pdf}[i][t + \\Gamma_{ij}]$ need $\\text{\\tt pdf}[i-1][t]$? This could use a better explanation.\n\n- In the learning via minimizing $H_{\\text{entropy}}$ for $v_m$, it seems that the values $p^y$ would need to be constantly updated when performing the line search. Is that correct? This is not clear from the notation.\n\n- The overall algorithm relies on the discretization level $\\Delta$ (selected as 100). What is effect of this size of discretization $\\Delta$ on the natural accuracy or certified accuracy? There must be a non-trivial tradeoff since a granular discretization would probably lead to a very noisy pdf while a coarser discretization would lead to a smoother one. Moreover, does the best level of discretization depend on the data (and if so how) or is a choice of discretization quite stable across datasets?\n\n\n- How is the proposed PDF computation extensible to arbitrary decision trees? It is mentioned in the discussion of limitations.\n", "limitations": "The authors explicitly address limitations and potential negative societal impact. One of the limitations (being unable to \"handle arbitrary ensembles of decision trees\") is related to the weakness I listed above. The authors claim that it is possible to extend to decision trees, but the extension seems non-trivial. However, the authors are upfront with this limitation.\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- This paper handles the robustness certification of a very widely used class of models -- ensembles of decision tree (stumps) -- and hence has the potential of significant impact given the wide use of such models in practical applications.\n\n- The paper provides a concise but sufficient background on randomized smoothing that allows the reader to understand the challenges that the proposed de-randomized smoothing is able circumvent.\n\n- It is very intuitive how the authors leverage the piecewise-constant structure in decision stump ensembles and the input randomization (independent across dimensions) to efficiently compute the output distribution. This is a great example of leveraging structure in the problem for efficient and accurate solutions. This efficient solution also allows the authors to develop a novel constructiion of robust decision tree stumps which would not have been possible without such an efficient computation of the output distribution.\n\n\nWeaknesses:\n\n- One weakness of the proposed scheme is the focus on decision stumps, which facilitates the creation of the per-feature meta-stumps, that are critical in the efficient computation. It is not clear how this technique would transfer to deeper decision trees since it is not clear to me how the meta-stumps could be created for such trees.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "c-_RQX9HgNj", "reviewer": "Reviewer_TjF1", "summary": "This paper deterministic smoothing for decision stump ensembles, and derive an MLE-optimal training method for smoothed decision stumps under randomization.", "questions": "1. The necessity of using randomized smoothing to provide the robustness guarantee for such a simple tree-based classifier, Decision Stump Ensembles. I think this paper might solve a simple problem (endowing Decision Stump Ensemble with certified robustness) in an overly complex way (randomized smoothing).\n\n2. Is the comparison to [Wang et al. 2020] in Table 2 is fair?  I think comparing smoothed decision stump ensemble (linear classifier) to naive decision stump ensemble (non-linear classifier) is unfair. It is unclear whether the improvement is for the superior performance of non-linear classifier or the certification method.\n\n\n[Wang et al. 2020] On lp-norm robustness of ensemble decision stumps and trees，ICML 2020.", "limitations": "The contribution of this paper is incremental. The paper just applies randomized smoothing to decision stump ensemble, and derives the robustness certificate for such a special classifier. The key contribution, deterministic certificate, is because of the overly simple structure of the base classifier (decision stump ensemble), instead of some new smoothing distributions (e.g., splitting noise [Levine et al., 2021]). We can also easily compute deterministic certificates for some other simple classifiers. For instance, we can derive the deterministic certificates for linear classifiers. The reason why we compute the probabilistic certificates for randomized smoothing is, the complex structure (almost black-box) of the neural network classifier. Moreover, I think the randomized smoothing for decision stump ensemble is only a simplified verison of the general problems studied in [Cohen et al., 2019] [Yang et al., 2020].\n\n[Levine et al., 2021] Improved, Deterministic Smoothing for L_1 Certified Robustness, ICML 2021.\n\n[Cohen et al., 2019] Certified adversarial robustness via randomized smoothing, ICML 2019.\n\n[Yang et al., 2020] Randomized smoothing of all shapes and sizes, ICML 2020.\n", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Good presentation \n\nWeaknesses:\n\n1.  The necessity of using randomized smoothing to provide the robustness guarantee for Decision Stump Ensemble. \n\n2. The contribution is incremental.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept