MABSplit: Faster Forest Training Using Multi-Armed Bandits
Authors: Mo Tiwari
Ryan Kang
Jaeyong Lee
Christopher J Piech
Ilan Shomorony
Sebastian Thrun
Martin Jinye Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: random forest
xgboost
CART
classification and regression trees
multi-armed bandits
best arm identification

Abstract: Random forests are some of the most widely used machine learning models today, especially in domains that necessitate interpretability. We present an algorithm that accelerates the training of random forests and other popular tree-based learning methods. At the core of our algorithm is a novel node-splitting subroutine, dubbed MABSplit, used to efficiently find split points when constructing decision trees. Our algorithm borrows techniques from the multi-armed bandit literature to judiciously determine how to allocate samples and computational power across candidate split points. We provide theoretical guarantees that MABSplit improves the sample complexity of each node split from linear to logarithmic in the number of data points. In some settings, MABSplit leads to 100x faster training (an 99% reduction in training time) without any decrease in generalization performance. We demonstrate similar speedups when MABSplit is used across a variety of forest-based variants, such as Extremely Random Forests and Random Patches. We also show our algorithm can be used in both classification and regression tasks. Finally, we show that MABSplit outperforms existing methods in generalization performance and feature importance calculations under a fixed computational budget. All of our experimental results are reproducible via a one-line script at https://github.com/ThrunGroup/FastForest.


MABSplit: Faster Forest Training Using Multi-Armed Bandits
Mo Tiwari'
Ryan Kangk*
Je-Yong Lee
Sebastian Thrun'
Chris Piech
Ilan Shomorony #
Martin Jinye Zhang #
Abstract
Random forests are some of the most widely used machine learning models today, especially in domains that necessitate interpretability. We present an algorithm that accelerates the training of random forests and other popular tree-based learn- ing methods. At the core of our algorithm is novel dubbed MABSplit, used to efficiently find split points when constructing decision trees. Our algorithm borrows techniques from the multi-armed bandit literature to judiciously determine how to allocate samples and computational power across candidate split points. We provide theoretical guarantees that MABSplit improves the sample complexity of each node split from linear to logarithmic in the number of data points. In some settings, MABSplit leads to 100x faster training (an 99% reduction training time) without any decrease in generalization performance. We demonstrate similar speedups when MABSplit is used across variety of forest-based variants, such as Extremely Random Forests and Random Patches. We also show algorithm can be used in both classification and regression tasks. Finally, we show that MABSplit outperforms existing methods in generalization performance and feature importance calculations under fixed computational budget. All of our experimental results are reproducible via a one-line script at https://github. cww http:hhhuunrouuppastooeeee.
subroutine,
Introduction
Random Forest (RF) is supervised learning technique that is widely used for classification and regression tasks 28 15 In RF, an ensemble of decision trees (DTss is trained for the same prediction task. Each DT consists of series of nodes that represent if if/then/en else comparisons on the feature output label. In RF, each DT is typically trained on bootstrup sample of original dataset and considers a random sample available features at each node split [14). The prediction of the each DT is aggregated to provide output label for the whole RF. By aggregating the prediction of each DT in the ensemble, RFs tend to be more robust to noise and overfitting [52] and are capable of capturing more complex patterns in the
values of a given datapoint and are used to produce
data than a single DT [59].
RF has gained tremendous popularity due to its flexibility, usefulness in multi-class classification and regression tasks, high performance across broad range of data types, natural support for missing features, and relatively low computational complexity [6]
53
10
35 30). Furthermore, RF inherits
denotes equal contribution. # denotes joint supervision. Conresoondence should be addressed to M.T. (motiwari @stanfordddd edu), I.S. dilansiillinois edd), and M.J.Z. (j (jinyzzhan@hhph. harvard, edu).
1: Department of Computer Science, Stanford University
2: Oxford University
3: Electrical and Computer Engineering, University of Illinois Urbana- Champaign
4: Department of Epidemiology. Harvard T.H. Chan School of Public Health
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the interpretability of decision trees because the prediction of each constituent DT can be explained through a sequence of binary decisions. RFs have been successfully applied in contexts as varied as the prediction of legal court decisions [32], solar radiation analysis [10], and the Higgs Boson classification problem [3 In the era of big data, a simple and flexible machine learning technique
such as RF is expected to play a key role in processing large datasets and providing accurate and
interpretable predictions.
The need for training prediction models on massive datasets and doing so on compute-constrained hardware, such as smartphones and tffernet-of-Thinge devices, requires the development of new algorithms that can deliver faster results without sacrificing generalization performance [6]]. For this reason, recent work has proposed ways to accelerate the training of RFs, both the algorithmic level and at the hardware level.
At the algorithmic level, most work focuses on fast construction of each individual DT. Each DT is built by identifying the feature f and threshold f that best split the data points according to the prediction targets. The data points are split into subsets based on whether their feature has a value less than or feature f has a value greater than t. The process is then recursed for each resulting subset. Most of the complexity in this process in identifying the pair (J.t) that provides the best split for set of N data points, which typically requires O(N) computation per split. Recent proposals include computing (or estimating) f and from subsample of the data points and features, or quantizing the feature values. The latter technique creates a histogram of values of each feature across the data points and restricts f be at the edges of histogram bins.
While existing approaches provide significant speed up in the training of RFs, they often require prespecification of fixed hyperparameters, such as the proportion of data points features to subsample, and are not adaptive to the underlying data distribution. Moreover, when comparing different candidate features for a split, all features are treated on equal footing and the quality of their split is computed based on the same number of data points. Intuitively, this is wasteful because features that are not informative for the prediction task can be identified based on a smaller number of data points. Alternatively, an adaptive scheme could better allocate computational resources towards a promising set of candidate features and achieve a better tradeoff between computational cost and generalization performance.
In this work, we propose MABSplit, fast subroutine for the node-splitting problem, which adaptively refines the estimate of the "quality" of each candidates be discarded early, which can lead to significant computational savings. The core idea behind our algorithm is to formulate the node-splitting task as a multi-armed bandit problem 34 2 58 where each pair (f, is a distinct arm. The unknown parameter of each arm, pft- corresponds to the quality of the split based on feature / and threshold I, where the split quality measured in terms of how much the split would reduce label impurity. An arm (f. t) can be "pulled" by computing the reduction of label impurity induced by new data point sampled from the dataset. This allows us to compute an estimate fa and a corresponding confidence interval, which can be used in a batched variant of the Upper Confidence Bound (UCB) and successive elimination algorithms [44 (3) to identify the best arm (f, Crucially, MABSplit uses the adaptive sampling tools of multi-armer bandits to avoid computing the split qualities over the entire dataset.
pair (f, t) as a candidate split. Bad split
We demonstrate the benefits of MABSplit on a variety of datasets, for both classification and regression tasks. In some settings, MABSplit algorithm leads to 100x faster training (a 99% reduction in training time), without any decrease in test accuracy, over an exact implementation of RF that searches for the optimal (f. t) pair via brute-force computation. Additionally, we demonstrate similar speedups when using MABSplit across a variety of forest-based variants, such as Extremely Random Forests and Random Patches.
1.1 Related work
Random Forests were originally proposed by Ho (28 In its original formulation, RF constructs Tueee DT's, where each DT is trained on bootstrap sample of all N' data points and a random subset of the features at each node (a technique known as random subspacing (29). More recently, the need
for training RFs on large datasets has prompted the development of several techniques to accelerate training at both the software and hardware levels.

---

Software acceleration of RF: Most of the software and algorithmic acceleration techniques focus on the training of each individual DT. FastForest [6]] accelerates the node-splitting task using three ideas: subsampling a pre-specified number of data points without replacement (subbagging), subsampling pre-specified number of features dependent on the current number of data points (Dynamic Restricted Subspacing), and dividing values of given feature into T bins, where T depends on the number of data points at the node (Logarithmic Split- Point Sampling, inspired by the single-tree SPAARC algorithm (62).. MABSplit is inspired by the ideas in FastForest, but does not require the number of data points or features to be prespecified and, instead, determines them by adapting to the data distribution.
Other recent work has also used adaptivity to identify the best split. For example, Very Fast Decision Trees (VFDTs) [19] and Extremely Fast Decision Trees (EFDTs) [40] are incremental decision tree learning algorithms in which trees can be updated in streaming settings. Acceleration of the node-splittng task is achieved by adaptively selecting subset of data points sufficient to distinguish the best and second best splits. These approaches are similar to ours, but the sampled data points are used to evaluate all possible splits. MABSplit, in contrast, adaptively discards unpromising splits early. The F-forest (23) algorithm also applies adaptivity and uses an upper bound on the impurity reduction of each split in order to discard candidate splits. This is similar in spirit to the goal of MABSplit, but is based on deterministic, conservative upper bound on the impurity reduction (as opposed to MABSplit's 's statistical estimate) and incurs computation linear in the node size for each split, even when considering a fixed number of possible split thresholds per feature.
Other variations of RF have been proposed to improve training time. Random Patches trees based on a subset of data points and features that is fixed for each entire forest. ExtraTrees (ET') 24 draw random subset of K features at each node and, for each one, chooses a number R of random splits. It then selects the split that yields the largest impurity reduction from among these KR candidate splits.
39 builds
Other recent work attempts accelerate RF training by identifying the optimal number of decision trees needed in the forest [5), a form of hyperparameter tuning. The MABSplit subroutine can also be incorporated into these methods.
Hardware acceleration of RF: The training of RFs can also be significantly accelerated through the use of specialized hardware. For instance, the implementation of RF available in Weka (21) allows trees to be trained on different cores and reduces forest training time. A GPU-based parallel implementation of RF has also been proposed in (26). These solutions require specialized hardware (e.g., GPU- PC video cards) and are inappropriate for everyday users locally executing data-
mining tasks on standard PCs or smartphones. As such, is still desirable to develop techniques to
improve prediction performance and processing speed at an algorithmic, plafforn-inndependet level.
2 Preliminaries
We now formally describe the RF algorithm and other tree-based models, all of which rely on node- splitting subroutine. We consider N data points {(x; [ where each x; is an M-ddmensional feature vector and y; is its target. Following standard literature, we consider flexible feature types such as numerical or categorical. We consider both categorical targets for classification and numerical targets for regression. With a slight abuse of notation, we use X' to mean either the set of indices {i) or the values {(x,, w:)}. with the meaning clear from context.
An RF contains Nuree decision trees, each trained a set of N bootstrapped data points (sampled with replacement) and a random subset of features at each node. The whole RF, an ensemble model, outputs the trees' majority vote in classification and the trees' average prediction in regression [28 15). We focus on the top-down approach of constructing DTs by choosing the feature- threshol pair at each step that best splits the set of targets given node (52).
We now discuss the method by which the best split chosen in each node. Consider a node with data points X' and m features F. Note that n and m at the given node may or may not be the same as N and M of the entire dataset (for example, RF considers a random subset of m = vM features at each node [12). Let Xt,, and Xx./t be the left and right child subsets of when X' is split according to feature of at threshold t. The approach finds the split that best reduces the label
3

---

impurity; i.e., finds
5c I sc) n
[RR.1e] (( 1 (22),
f,t arg min feF
+
(1)
n
where I(S) measures the impurity of targets {y: and Ty is the set of allowed thresholds for feature f. Common impurity measures include Gini impurity or entropy for classification, and mean-squared -eroor (MSE) for regression [[6]:
K
K
1 12
Gini : : 1--1- E Pk
Entropy: :
Σ
Pk log2 Pk.
MSE
Σ EE
vy 7)
(2)
where K is the total number of classes and ps = E I(:: = k) is the proportion of class k in X' in classification, and ý = 1/4 Eiex Di is the average target value in regression. We note that our proposed algorithm, MABSplit, does not assume any particular structure of (()).
While the conventional RF considers all (n 1) possible splits among the n generally different values in the dataset for given feature f. in this work we focus on the histogram- bbaed variant that chooses the threshold from a set of predefined values T,, e.g., [Tyl equally-sacced histogram bin edges; this variant is substantially more efficient, offers comparable accuracy, and has been used in most state-of-the-arr implementations such as XGBoost and LightGBM [51] 17
33 62) A naïve algorithm finds the best feature-threste threshold pairs in Equationh ① by evaluating the label impurity reduction for each feature-threshold over all n data points, which incurs computation linear in n.
3 MABSplit
We now discuss MABSplit and how can reduce the complexity of the node-splitting problem to logarithmic in n.
With the same notation in Section
2
note that Equation (1 is equivalent to
ft, I( + [. ((Kg,fe)
f" arg min SER,eETy n
(3)
n
and so focus on solving Equation 33) Let jeft |2ا I(X + [2 1 (( be the
optimization objective for feature- thrresold pair (f. Omitting the dependence on K, computing Mys exactly is at least On)) MABSplit, however, estimates juze with less computation by drawing n' < independent samples with replacement from X. As shown in Subsec. 3.1 it is possible to
construct point estimate (n') and (1 1- d) confidence interval (CI) C 8) for the parameter
Hft, where n' and 5 determine estimation accuracy. The width of these CIs generally scales with
1/6 To estimate the solution to Problem 3 with high confidence, we can then choose sample
x²'
different amounts of data points for different features so as to estimate their impurity reductions to varying degrees of accuracy. Intuitively, promising features-threshold splits with high impurity reductions (lower values of (*fe) should be estimated with high accuracy with many data points, while less promising ones with low impurity reductions (higher values of (1fz) can be discarded early.
The exact adaptive estimation procedure, MABSplit, is described in Algorithm ! It can be viewed as batched version of the conventional UCB algorithm [34] 63 combined with successive elimination [22] is straightforward to implement, and has been used other applications [58] 55 56 6 7
Algorithm| I Juses the set Sualution to track all potential solutions to Problem (3): Syotation is initialized as the set of all feature-threshold pairs {(f, t)} and Algorithm I maintains the mean objective estimate
As and (1 ---6) 6) CI Cft for each potential solution (f, soluuton
In each iteration, new batch of data points Xoutch used evaluate the split quality for all potential thrresrld splits in Syotutions which allows the estimate of each ğa to be made more accurate. Based on the current estimate, a candidate's lower confidence bound pi.t - Cft greater than the upper confidence bound of the most promising candidate min + Ctt), we remove it from Syatution- This process continues until there is only one candidate in Ssolution or until we have sampled more than n data points. In the latter case, we know that the difference between the remaining candidates in Seatution is so subtle that an exact computation warranted. MABSplit then compute those candidates' objectives exactly and returns the best candidate in the set.

---

3.1 Point estimates and confidence intervals for impurity metrics
We now discuss MABSplit's construction of point estimates and confidence intervals μf based on set of n' points, {(,,, Y:)),= sampled independently and with replacement from X. We consider two widely used impurity metrics in classification, Gini impurity and entropy, although mean estimates and confidence intervals for other settings and metrics can be derived similarly (more details provided in Appendix 3
Let Pt..A 1
>i= Iews < 4i44 = k) and PR.A == + - May 2 1, = k) denote the proportion of the full data points in class & and each of the two subsets created by the split (f, (we call these subsets "left" and "right", respectively). Note that
sc and Σ PR. A
FR
EPLA
PLR
"
Furthermore, let PL,A == 1 Σn I(Xis S,YY, k) and Pu, 1 E 1(X,, ,,Y; k) denote the empirical estimates of pi,k and PR,& based the n' subsamples drawn thus far. Then k PR, } jointly follow multinomial distribution satisfying
E = pr.Rs Varlfr.u] = n Pr -PI,k);
E L PR,K:
VarlpR,u] PR. PR.x).
since for each random data point (X;, Yi), exactly one element of the set & PR. 1K is incre-
mented. Using Equations ( and 4p. and the definition of p& after Equation (3), we write
Gini impurity pitt = ExPh.
ER
(5)
ΣxPL. PL,k
Σx PR.K
Entropy Hft = =- Σ P log2
Pl,,k
Σ
PR.A log2
PR.&
(6)
Ev PL,K
Ex PR.
k
where the empirical parameters (PL, PR. I as plug-in estimators for the true parame- ters {Pr.k. P k=1 to produce the point estimate ft
In MABSplit (Algorithm) D. each batch of data points used to update each fr., and PR,S, which are used in turn to update our point estimates Pitt and the corresponding Cls. The Cls of jazz are based on standard error derived using the delta method [60]. As standard applications of the delta method, the estimates fu asymptotically unbiased and their corresponding CIs are asymptotically valid. Appendix provides further details, including a derivation the CIs and discussion convergence properties.
3.2 Algorithmic and implementation details
We considered sampling with replacement in MABSplit (Algorithm) D primarily for the ease of theoretical analysis. In practice, we found sampling without replacement was more computationally efficient and did not significantly change the results, and was used the actual implementation.
For DTs, in classification tasks, we allow individual DTss to provide soft votes and average their pre- dicted class probabilities determine the forest's predicted class label, following existing approaches [7]. This is in contrast with hard votes, in which each DT is only permitted to produce its best label and the forest's 's prediction is determined by majority voting. For the fixed-budget experiments in Section [3] we terminate tree construction and do not split nodes further if doing so would violate our budget constraints.
Analysis of the Algorithm
In this section, prove that MABSplit returns the optimal feature-threshold pair for a node split with high probability. Furthermore, we provide bounds on computational complexity MABSplit, which can lead to logarithmic dependence the number of data points n under weak assumptions.
5

---

Algorithm MABSplit ( F,F, F,FF, ,T,, I(.), B,8)
Ssolation f- [(f.t), Vf F, Vt E Tr}
Set of potential solutions to Problem (3) D Number of data points sampled b Initialize mean and CI for each arm
2: Mused f- 0
3: For all (f.t)
Ssolutions set Pigt +- 00, Cft t 0o
4: for all f E F do
5:
Create empty histogram, hy. with [Tyl equally spaced bins 6: while Rossed < and salltionn > 1 do
7:
Draw batch sample Xbatc of size with replacement from X
8:
for all unique f in Soluttoon do
9:
for all Xbatch do
10:
Insert xy into histogram h
D. Each insertion is O())
for all (f,t) E Saolution do
12:
Update Byt and Ct: based on histogram by
For fixed f. this is O(T)
13:
Suotution f {(S, t): jtst Cp S min C₁t)
> Retain only promising splits
14:
Tussd
Puxsed + B
15:
if
SSolution| then
16:
return (f", (*) E Ssolution
17:
else
18:
Compute fe exactly for all (f.t)= E Ssolution
19:
return (f*,t") arg (f.t)) Pft
As above, consider a node with n data points X, m features F, and T possible thresholds for each feature ([Tyl = T for all f). Suppose (f*,t*)= arg min jft is the optimal feature- threshold pair which to split the node. For any other feature-threshold pair (f,t), define Ast == Fft - 1' To state the following results, we will assume that, for a fixed feature-threshold pair tf,t) and n' randomly sampled datapoints, the (1 - 8) confidence interval scales as Cfe(n', 6)
O(y
(This assumption is justified for the confidence intervals of Gini impurity and entropy under weak assumptions the f, 60)). With this assumption, we state the following theorem:
log 1/6
Theorem 1. Assume Ico 0 s.t. AA > 0, n > O, have Cfr(n', , 8) < co
log 1/6 For 0 mm
with probability at least 1 n. Algorithm I returns the correct solution to Equation Furthermore, Algorithm 7 Juses a total of M computations, where
4c8 A
E|M] <
Σ
min
log(n'mT) + B, 2n + 2mT.
JEF,IET,
ft
Theorem is proven in Appendix I Intuitively, Theorem I Itates that with high probability. MABSplit returns the optimal feature-threshold pair at which to split the node. The bound Equation 77) suggests
the computational cost of a thature-d pair (J, t). i.e., min 4e B
log(n>m()) + B, 2n de-
pends on A which measures how close its optimization parameter y to perr Most reasonably different features f * f will have a large A and incur computational cost Oloo(n)²mT)) that is sublinear n.
In turn, this implies MABSplit takes only O(mT log(n2m(T)) computations per feature-threshold pair if there is reasonable heterogeneity among them. As proven in Appendix of (5). this is the case under wide range of distributional assumptions on the f 's, e.g., when the ut 's follow a sub- Gaussian distribution across the pairs (f.t). Such assumptions ensure that MABSplit has an overall complexity of (mm log(n mT)),, which is sublinear in the number of data points n. We note that in the worst case, however, MABSplit may take O(n(m + T)) computations per feature thrreshold pair when most splits are equally good, in which case MABSplit reduces to batched version of the naive al algorithm. This may happen, for example, highly symmetric datasets where all splits reduce the impurity equally. Other recent work provides further discussion on the conversion between a bound like Equation 77). which depends on the A,'s, and a bound in terms of other problem parameters such
as O(mi log n m?]) under various assumptions the uyz" 's [5] 63 7 58 4 6).

---

Finally, we note that å is hyperparameter governing the error rate. It is possible to prove results analogous Theorem for arbitrary 8.
Experimental Results
We demonstrate the advantages of MABSplit in two settings. In the first setting, the baseline models with and without MABSplit are trained to completion and report wall-clock training time and generalization performance. In the second setting, we consider training each forest with a fixed computational budget and study effect of MABSplit on generalization performance. We provide description of each dataset in Appendix 6
We note that head-to-head wall-clock time comparisons with common implementations of forest- based algorithms,, such as Weka's 's [20) or scikit-leare hardware- and language-level optimizations. As such, we reimplement these baselines in Python and focus on algorithmic improvements. The only difference between our model and the baselines is the call to the node-splitting subroutine (MABSplit in model, and the exact, brute- solver for the baseline models); thus, any improvements in runtime are due to improvements the node- splitting algorithm. This is verified by profiling the implementations and measuring the relative time spent in the node-splitting subroutine versus total runtime (see Appendix 5). Our approach allows us focus algorithmic improvements opposed implementation- sepciooi optimizations. Our implementation of these baselines may also be of independent interest and we verify the quality of our implementations, via agreement with scikit-learr, in Appendix 4 We also provide brief discussion of how an optimized version of our reimplementations may outperform scikit- Malkit-leaan in On the MNIST dataset, our optimized implementation trains approximately 4x faster than scikit- -earnn's 's DecisionTrreelasssee
[48], would be unfair due to their extensive
Appendix 7
Baseline Models: We compare the histogrammed versions of three baselines with and without MABSplit: Random Forest (RF), ExtraTrees [24]. and Random Patches (RP) [39]. In Random Forests, each tree fits a bootstrap sample of N datapoints and considers random subset of VM features every node split. Extra Trees (also known as Extremely Randomized Forests) are identical to Random Forests except for two differences. First, in regression problems, all features are considered at every node split (in classification problems, we still use only v VM features). Second, the histogram edges of feature are randomly chosen from uniform distribution maximum value. In classification problems, each histogram has VM bins and in regression problems, each histogram has M bins. These conventions follow standard implementations [47). Note that in ExtraTrrees, the bins in feature's 's histogram need not be equally spaced. Random Patches is identical to Random Forests but the training dataset is reduced to 0n, of its original datapoints and a of its original features, where an and y are prespecified constants, and the subsampled dataset is fixed for the training of the entire forest. Full settings for all experiments are given in Appendix 6
that feature's 's minimum and
5.1 Wall-clock time comparisons
In the first setting, we compare baseline models with and without MABSplit in terms of wall-clock training time. Tables D and 2 show that MABSplit provides similar generalization performance but faster training than the usual naïve algorithm for node-splitting for almost all basclines both classification and regression tasks. Across various tasks, MABSplit leads to approximately 2x- 100x faster training, a reduction of training time of 50-99%. These benefits are wholly attributable to MABSplit as the only difference between successive minor rows in each table is the node-splitting subroutine (see Appendix 5 for further discussion).
5.2 Fixed budget comparisons
In the second setting, we consider training models under a fixed computational budget. As before, insertion into a histogram is taken to be an O(1) operation. This is justified if the histogram's 's thresholds are evenly spaced, wherefore the correct bin in which to insert value can indexed into directly. (If the bins are unevenly spaced, we may perform binary searches to locate the correct bin, which Ollog T) and does not depend on n, or cache the results of these binary searches for an evenly-spaced grid across the range of the given feature's value.)
7

---

MNIST Dataset (NV
000)
Model
Training Time (8)
Number of Insertions
Test Accuracy
RF
1542.83 5.837
1.44F+08 + 4.85E+05
0.777 E 0.005
RF + MABSplit
40.359 + 0.246
3.37E+06 # 1.62E+04
0.763 = 0.008
Extra Trees
1789.653 1 2.396
1.68E+08 1 0.00E+000
0.762 1 0.003
ExtraTrees MABSplic
50.217 0.304
4.32E:406 + 7.69E+003
0.755 + 0.002
RP
1421.963 8.368
1.32E:088 + 6.95E:405
0.771 + 0.003
RP MABSplit
38.415 0.245
3.17E+06 1.40E+04
0.768 + 0.003
APS Failure at Scania Trucks Dataset (JV
60, 000)
Model
Training Time (8)
Number of Insertions
Accuracy
RF
20.542 = 0.048
3.77E406 + 9.66E403
0.985 + 0.0
RF + MABSplit
0.455 1 0.002
6.94E+004 1 2.19E+02
0.985 1
Extra Trees
18.849 1 0.027
3.78E+06 1. 0. 0.00E++00
0.985 1 0.0
ExtraTrees + MABSplit
0.406 + 0.001
7.00E+04 + 0.00E+00
0.985 + 0.0
RP
17.63 1 0.054
3.22E:06 1: 1.18E+04
0.985 1
RP MABSplit
0.399 + 0.003
5.96F++04 + 2.19F+02
0.985 + 0.0
Forest Covertype Dataset Training Time (s)
012) Number of Insertions
Model
Test Accuracy
RF
117.351 0.123
1.86E+07 1 0.00E+00
0.359 1 0.028
MABSplit
0.88 0.009
3,98E+04 + 1.79E+02
0.505 + 0.004
Extra Trees
117.984 = 0.119
186E+07 = 0.00E+00
0,539 + 0.022
ExtraTrees + MABSplit
2.942 = 0.856
3.69E+05 =: 1.22E+05
0.5 0.005
RP RP MABSplit
104.456 0.737
1.62F:007 + 8..1F+004
0.51 + 0.008
0.815 = 0.004
3,50E+04 = 0.00E+00
0.507 + 0.005
Table 1:
Wall-clock training time, number of histogram insertions, and test accuracies for various models with and without MABSplit. MABSplit can accelerate these models by over 100x some cases (an 99% reduction in training time) while achieving comparable accuracy. The number of histogram insertions correlates strongly with wall-clock training time, which justifies our focus on accelerating the node-spliting algorithm via reductions in sample complexity.
Beijing Multi-Site Air-Quality Dataset (Regression,
420, 768)
Model
Training Time (s)
Test MSE
RF
138.782 + 1.581
1164.576 + 0.761
RF + MABSplit
67.089 + 1.682
1109.542 23.776
Extra'Tres
115.592 + 3.061
1028.054 11.355
ExtraTrees MABSplit
53.607 + 1.278
1015.234 + 6.535
RP
108.174 1.24
1128.299 25.78
RP MABSplit
60.639 = 3.642
1125.816 + 33,56
SGEMM GPU Kerne Performance Dataset (Regression, N = 241, 600)
Model
Training Time (s)
Test MSE
RF
32.606 = 0.859
69733.002 + 57.401
RF MABSplit
16.51 + 0.224
69493.921 +'2 73.133
ExtraTrees
30.624 + 0.686
69734.948 + 54.876
ExtraTrees + MABSplit
14.086 = 0.295
69585.029 + 80.281
RP
26.091 = 0.417
66364.998 - 894.568
RP MABSplit
16.409 + 0.952
66310.138 896.237
Table 2: Wall-clock training time and test MSEs for various models with and without MABSplit.
MABSplit accelerate these models by up 2x (an 50% reduction in training time) while achieving comparable results. We omit the number of histogram insertions in favor of wall-clock time for simplicity; unlike in classification, the different baseline regression models have widely varying histogram bin counts. Since the histogram insertion complexity is different across models, the comparison across models would not be fair.

---

MNIST Dataset (N 60, 000)
Model
Number of Trees
Test Accuracy
RF
0.2 = 0.179
0.143 = 0.026
RF + MABSplit
15.8 + 0.179
0.83 0.002
Extra
0.2 0.179
0.144 + 0.027
ExtraTrees MABSplit
12.0 = 0.0
0.814 + 0.001
RP
1.0 + 0.0
0.253 + 0.003
RP + MABSplit
16.8 0.179
0.832 0.002
APS Failure at Scania Trucks Dataset (N 60, 000)
Model
Number of Trees
Test Accuracy
RF
1.0 + 0.0
0.985 + 0.0
RF + MABSplit
5.8 0.179
0.989 + 0.0
Extra Trees
1.0 = 0.0
0,985 = 0.0
ExtraTrees MABSplit
5.6 0.219
0.989 + 0.0
RP
1.0 + 0.0
0.985 + 0.0
RP + MABSplit
6.8 0.179
0.989 + 0.0
Forest Covertype Dataset (N = 581, 012)
Model
Number of Trees
Test Accuracy
RF
0..4 + 0.219
0.514 + 0.0T9
RF + MABSplit
99.8 + 0.179
0.675 + 0.002
ExtraTrees
0.2 + 0.179
0.496 + 0.006
ExtraTrees MABSplit
23.4 +: 1.403
0.677 + 0.002
RP
0.6 0.219
0.534 4 0.03
RP + MABSplit
100.0 + 0.0
0.675 + 0.002
Table 3:
Classification performance under fixed computational budget (number of histogram insertions) for various models with and without MABSplit. MABSplit allows for more trees to be trained and leads to better generalization performance.
Intuitively, the MABSplit algorithm allows for splitting a given node with less data point queries and histogram insertions than the naïve solution. As such, when the computational budget fixed, forests trained with MABSplit should be able to split more nodes and therefore train more trees than forests trained with the naive solver. Prior work suggests that increasing the number of trees in a forest improves generalization performance by reducing variance at the cost of slightly increased bias [27].
Tables 3 and demonstrate the generalization performance of different models the computational budget is held constant for different classification and regression tasks. When using MABSplit, the trained forests consist more trees and demonstrate better generalization performance across all baseline models.
5.3 Feature stability comparisons
We also apply MABSplit compute feature importances under fixed budget. We follow the common approach of computing the feature importances of multiple forests and then measuring the stability of feature selection across forests using Permutation Feature Importance and Mean (see Appendix for further discussion of these metrics). The forests trained with MABSplit demonstrate better feature stabilities than those trained with the naïve algorithm; see Table Note that the datasets used for these experiments are different from the real-world datasets used the other experiments and are described in Appendix 6
Decrease in Impurity (MDI) 42 49
Discussions and Conclusions
In this work, we presented a novel algorithm, MABSplit, for determining the optimal feature and corresponding threshold at which to split node in tree-based learning models. Unlike prior models such as Random Patches, which the subsampling hyperparameters an, and a must be prespecified manually, MABSplit requires tuning and queries only much data as is needed by virtue of its

---

Beijing Multi-Sine Air-Quality Dataset (N 768)
Model
Number of Trees
Test MSE
RF
0.0 I 0.0
3208.93 = 0.0
RF + MABSplit
12.0 0.0
927.013 + 2.042
RP RP MABSplit
0.0 = 0.0
3208.93 0.0
11.0 + 0.4
875.764 = 3.064
ExtraTrees
0.0 + 0.0
3208.93 + 0.0
ExtraTrees + MABSplit
9.0 + 0.0
834.338 + 4.377
SGEMM GPU Kernel Performance Dataset (N
241, 600)
Model
Number of Trees
Test MSE
RF
0.0 + 0.0
131323.839 + 0.0
RF + MABSplit
5.6 + 0.219
28571.393 + 357.433
RP
0.8 = 0.179
102616.047 = 6647.02
RP MABSplit
2.8 + 0.593
64876.329 + 13350.921
Fres
0.0 + 0.0
131323.839 + 0.0
ExtraTrees + MABSplit
5.0 + 0.0
29919.254 + 344.409
Table 4: Regression performance under fixed computational budget (number of histogram inser-
tions). MABSplit allows for more trees to be trained and leads to better generalization performance.
Importance Model
Stability Metric
Dataset
Stability
RF RF MABSplit
MDI
Random Classification
0.536 = 0.039
MDI
Random Classification
0.863 + 0.016
RF
MDI
Random Regression
0.134 1 0.021
RF + MABSplit
MDI
Random Regression
0.674 + 0.043
RF
Permutation
Random Classification
0.579 + 0.023
+ MABSplit
Permutation
Random Classification
0.69 + 0.023
RF RF MABSplit
Permutation
Random Regression
0.116 = 0.017
Permutation
Random Regression
0.437 + 0.044
Table 5: Stability scores under a fixed computational budget (number histogram insertions).
MABSplit allows more trees to be trained, which Ieads to greater feature stabilities across the forests.
adaptivity to the data distribution. Indeed, robustness to choice of hyperparameters is one of primary appeals of algorithms like RF [50].
MABSplit avoids the expensive O(nlogn) sort used in many existing baselines and the (nn) com- putational complexity of their corresponding histogrammed versions. MABSplit can be used in conjunction with existing software- and hardware-specific optimizations and with other methods such as Logarithmic Split-Point Sampling and boosting [61]. In boosting, MABSplit has the potential advantage of only needing update data points' targets on-the-fly, as needed by its sampling, as opposed to current approaches that update targets for the entire dataset at each iteration. Addition- ally, MABSplit may permit easier parallelization due to lower memory requirements than existing algorithms, which may enable greater use in edge computing and may be adaptable to streaming settings.
We also note that logn" term in the complexity of MABSplit (Equation 7 comes from a union bound over all possible n² confidence intervals computed for each feature-threshold pair across all stages of the algorithm (see the proof of Theorem in Appendix [b. This union bound may be weak. Instcad, one more precisely compute the number of confidence intervals in terms of the arm gaps (the A,'s) In this way, the complexity result (Equation 7 can be phrased in terms of the A, instead of n. Intuitively, this would lead to complexity bound in terms of the aata-generating distribution that is independent of dataset size. Indeed, this is how complexity results are usually stated for multi-armed bandit algorithms [I]. We leave more detailed investigation of this topic to future work.
Acknowledgements:: M. T. was funded by a J.P. Morgan Fellowship, a Stanford Indisciplinary Graduate Fellowship, a Stanford Data Science Scholarship. and an Oak Ridge Institute for Science and Engineering Fellowship. M.J.Z. supported by NIH grant ROI MH1 15676. I. S. was supported in part by the National Science Foundation (NSF) under grant CCF-2046991.
10

---

References
[1] Serhat Arslan, Mo Tiwari, and Chris Piech. Using google search trends to estimate global patterns in learning. In Proceedings of the Seventh ACM Conference on Learning @ Scale, L@S 220, page 185-195, New York, NY, USA, 2020. Association for Computing Machinery.
[2] Jvan-Yves Audibert, Sébastien Bubeck, and Rémi Munos. Best identification in multi-armed bandits. In International Conference on Learning Theory, pages 41-53, 2010.
[3] Mourad Azhari, Abdallah Abarda, Badia Ettaki, Jamal Zerouaoui, and Mohamed Dakkon. Higgs boson discovery using machine learning methods with pyspark. Procedia Computer Science, 170:1 10111111140 1166, 2020.
[4] Vivek Bagaria, Tavor Z Baharav, Govinda M Kamath, and N Tse David. Bandit-based monte carlo optimization for nearest neighbors. IEEE Journal on Selected Areas in Information Theory, 2(2):599-610, 2021.
[5] Vivek Bagaria, Govinda M. Kamath, Vasilis Ntranos, Martin Zhang, and David Tse. Medoids in almost-linear time via multi-armed bandits. In International Conference on Artificial Intelli- gence and Statistics, pages 500-509, 2018.
[6] Tavor Baharav, Gary Cheng, Mert Pilanci, and David Tse. Approximate function evaluation via multi-armed bandits. In International Conference Artificial Intelligence and Statistics, pages 105-135. PMLR, 2022.
[7] Tavor Z. Baharav and David Tse. Ultra fast medoid identification via correlated sequential halving. In Advances in Neural Information Processing Systems, pages 3650-3659, 2019.
[8] Rafael Ballester-Ripoll Enrique G. Paredes, and Renato Pajarola. Sobol tensor trains for global sensitivity analysis. CoRR, abs/1712.00233, 2017.
[9] G. P. Basharin. On statistical estimate for the entropy of a sequence of independent random variables. Theory of Probability & Its Applications, 4(3):333- 1959.
[10] Lamara Benali, Gilles Notton, A Fouilloy, Cyril Voyant, and Rabah Dizene, Solar radiation forecasting using artificial neural network and random forest methods: Application to normal beam, horizontal diffuse and global components. Renewable energy, 132:871-884, 2019.
[11] Yoshua Bengio, Tristan Deleu, Edward J. Hu, Salem Lahlou, Mo Tiwari, and Emmanuel Bengio. Gflownet foundations. CoRR, abs/21 11 1.09266. 2021.
[12] Simon Bernard, Laurent Heutte, and Sébastien Adam. Influence of hyperparameters on random forest accuracy. In International workshop on multiple classifier systems, pages 171-180. Springer, 2009.
[13] Jock Blackard and Denis Dean. Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables. Computers and Electronics in Agriculurr, 24:131-151, 12 1999.
[14] Leo Breiman. Bagging predictors. Machine learning, 2432):1 1996.
[15] Leo Breiman. Random forests. Machine learning, 45(1):5 5-32 2001.
[16] Leo Breiman, Jerome H Friedman, Richard A Olshen, and Charles Stone. Classification and regression Irees. Routledge, 2017.
[17] Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd aem sigkdd international conference on knowledge discovery and data mining, pages 785-794, 2016.
[18) Kaustubh D. Dhole et al. Nl-augmenter: A framework for task-sensitive natural language augmentation, 2021.
[19] Pedro Domingos and Geoff Hulten. Mining high-speed data streams. In Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 71-80, 2000.
[20] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
[21] Frank Eibe, Mark A Hall, and Ian H Witten. The weka workbench. online appendix for data mining: practical machine learning tools and techniques. In Morgan Kaufmann. Elsevier Amsterdam, The Netherlands, 2016.

---

[22] Eyal Even- Dee,,Dar, Shie Mannor, and Yishay Mansour. Action elimination and stopping conditions for the multi- armed bandit and reinforcement learning problems. In Journal of Machine Learning Research, volume 7, pages 1079-11055 2006.
[23] Yasuhiro Fujiwara, Yasutoshi Ida, Sekitoshi Kanai, Atsutoshi Kumagai, Junya Arai, and Naonori Ueda. Fast random forest algorithm via incremental upper bound. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pages 2205-22002220 2019.
[24] Pierre Geurts, Damien Ernst, and Louis Wehenkel. Extremely randomized trees. Machine learning, 63(1):3-42, 2006.
[25] Christopher Gondek, Daniel Hafner, and Oliver R. Sampson. Prediction of failures in the air pressure system of scania trucks using a random forest and feature engineering. In Henrik Boström, Arno Knobbe, Carlos Soares, and Panagiotis Papapetrou, editors, Advances in Intelli- gent Data Analysis XV, number 9897 in Lecture Notes Computer Science, pages 398-402 402, Cham, 2016. Springer International Publishing.
[26] Hakan Grahn, Niklas Lavesson, Mikael Hellborg Lapajne, and Daniel Slat. Cudarf: a cuda- based implementation of random forests. In 2011 9th IEEE/ACS International Conference on Computer Systems and Applications (AICCSA), pages 95-101. IEEE, 2011.
[27] Trevor Hastie, Robert Tibshirani, and Jerome H. Friedman. Elements of Statistical Learning. Springer, 2009.
[28] Tin Kam Ho. Random decision forests. In Proceedings of 3rd international conference on document analysis and recognition, volume 1, pages 278-282, IEEE, 1995.
[29] Tin Kam Ho. The random subspace method for constructing decision forests. IEEE transactions on pattern analysis and machine intelligence, 20(8):832-844, 1998.
[30] Gareth James, Daniela Witten, Trevor Hastie, and Robert Tibshirani. An introduction to statistical learning, volume 112. Springer, 2013.
[31] Kevin Jamieson and Robert Nowak. Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In Annual Conference on Information Sciences and Systems, pages 1-6, 2014.
[32] Daniel Martin Katz, Michael Bommarito, and Josh Blackman. A general approach for predicting the behavior of the supreme court of the united states. PloS one, ((4)=00174695 2017.
[33] Guolin Ke, Qi Meng. Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie- Yan Liu. Lightgbm: A highly efficient gradient boosting decision tree. Advances in neural information processing systems, 30, 2017.
[34] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Ad- vances in applied mathematics, 6(1):4-22, 1985.
[35] SK Lakshmanaprabu, K Shankar, M Ilayaraja, Abdul Wahid Nasir, V Vijayakumar, and Naveen Chilamkurti. Random forest for big data classification in the internet of things using optimal features. International journal of machine learning and cybernetics, 10(10):269--260 8, 2019.
[36] Siu Kwan Lam, Antoine Pitrou, and Stanley Seibert. Numba: A llvm-based python jit compiler. In Proceedings of the Second Workshop on the LLVM Compiler Infrastructure HPC, LLVM 15, New York, NY, USA, 2015. Association for Computing Machinery.
[37] Gabriele Lanaro, Quan Nguyen, and Sakis Kasampalis. Advanced Python Programming: apps with Python using proven design
Build high performance, concurrent, and patterns. Packt Publishing.
[38] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 86(1 (6(11))2278-233 1998.
[39] Gilles Louppe and Pierre Geurts. Ensembles on random patches. In Joins European Conference on Machine Learning and Knowledge Discovery in Databases, pages 346-361. Springer, 2012.
[40] Chaitanya Manapragada, Geoffrey I Webb, and Mahsa Salehi. Extremely fast decision tree. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1953-1962, 2018
12

---

[41] Ali Mohsen and Mo Tiwari. Image compression and classification using qubits and quantum deep learning, 2021.
[42] Kristin K. Nicodemus. Letter to the editor: On the stability and ranking of predictors from random forest variable importance measures. Briefings in Bioinformatics, 12(():369-31) -3733,9933,,,0 04 2011.
[43] Sarah Nogueira, Konstantinos Sechidis, and Gavin Brown. On the stability of feature selection algorithms. J. Mach. Learn. Res., 18(1):6345-638 2017.
[44] Cedric Nugteren and Valeriu Codreanu. Cltun: A generic auto-tuner for opencl kernels. In 2015 IEEE 9th International Symposium on Embedded Multicore/Mnny-ore Dystems-on-Chip
pages 195-202, 2015.
[45] Thais Mayumi Oshiro, Pedro Santoro Perez, and José Augusto Baranauskas. How many trees in random forest? In International workshop on machine learning and data mining in pattern recognition, pages 154-168. Springer, 2012.
[46] Liam Paninski. Estimation of entropy and mutual information. Neural Comput., 191-:13 jun 2003.
[47] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python, Journal of Machine Learning Research, 12:2825-288 2830. 2011.
[48] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit- learn: Machine learning in python. The Journal of Machine Learming Research, 12:2825-2830. 2011.
[49] Miriam Piles, Rob Bergsma, Daniel Gianola, Hélène Gilbert, and Llibertat Tusell. Feature selection stability and accuracy of prediction models for genomic prediction of residual feed intake in pigs using machine learning. Frontiers in Genetics, 12, 2021.
[50] Philipp Probst, Marvin Wright, and Anne-Laure Boulesteix. Hyperparameters and tuning strategies for random forest. Wiley Interdisciplinary Reviews: data mining and knowledge discovery, 9(3): 11311 2019.
[51] Sanjay Ranka and Vineet Singh. Clouds: A decision tree classifier for large datasets. In Proceedings of the 4th knowledge discovery and data mining conference, volume 2, 1998.
[52] Lior Rokach and Oded Maimon. Top-down induction of decision trees classifiers-a survey. IEEE Transactions on Systems, Man, and Cybernetics, Part (Applications and Reviews), 35(4):476-48) 2005.
[53] Eduarda MO Silveira, Sergio Henrique G Silva, Fausto W Acerbi-Junior, Monica C Carvalho, Luis Marcelo T Carvalho, Jose Roberto Scolforo, and Michael Wulder. Object- based random forest modelling of aboveground forest biomass outperforms pixel-based approach in a heterogeneous and mountain tropical environment. International Journal of Applied Earth Observation and Geoinformation. 78:175-188 2019.
[54] Aarohi Srivastava et al. Beyond the imitation game: Quantifying and extrapolating the capabili- ties of language models, 2022.
[55] Mo Tiwari, Ryan Kang. Je- Yong" Lee, Sebastian Thrun, Martin Zhang, and Ilan Shomorony. Faster maximum inner product search in high dimensions. Preprint.
[56] Mo Tiwari, Ryan* Kang, Luke* Lee, Sebastian Thrun, Martin Zhang, Ilan Shomorony, and Chris Piech. Intelligent caching for sequential, permutation -initttiiionnnnaiaanttt multi-armed bandits. Preprint.
[57] Mo Tiwari, Chris Piech, Medina Baitemirova, Namperumalsamy Prajna, Muthiah Srinivasan, Prajna Lalitha, Natacha Villegas, Niranjan Balachandar, Janice T Chua, Travis Redd, Thomas M Lietman, Sebastian Thrun, and Charles C Lin. Differentiation of active corneal infections from healed scars using deep learning. Ophthalmology, 129, 2022.
[58] Mo Tiwari, Martin J Zhang, James Mayclin, Sebastian Thrun, Chris Piech, and Ilan Shomorony, Banditpam: Almost linear time k-medoids clustering via multi-armed bandits. Advances in 2020.
Neural Information Processing Systems,
13

---

[59] Kagan Tumer and Joydeep Ghosh. Error correlation and enror reduction in ensemble classifiers. Connection science, 8(3-4):385 404, 1996.
[60] Aad W Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
[61]
Darren Yates and Md Zahidul Islam. Fastforest: Increasing random forest processing speed while maintaining accuracy. Information Sciences, 557:1 2021.
[62] Darren Yates, Md Zahidul Islam, and Junbin Gao. Spaarc: a fast decision tree algorithm. In Australasian Conference on Data Mining, pages 43-55. Springer, 2018.
[63] Martin Zhang, James Zou, and David Tse. Adaptive monte carlo multiple testing via multi-armed bandits. In International Conference on Machine Learning, pages 7512-7522, 2019.
[64] Shuyi Zhang, Bin Guo, Anlan Dong. Jing He, Ziping Xu, and Song Chen. Cautionary tales on air-quality improvement in beijing. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 473, 2017.
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 have all reviewed the claims in the abstract and introduction and confirmed that they reflect the paper's contributions and scope.
(b) Did you describe the limitations of your work? [Yes] We discuss the assumptions necessary for MABSplit to work in Section 4 and also discuss failure modes when these assumptions are violated. We also describe further room to improve our work in Section 6
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We discuss potential negative societal impacts in the Future Work section
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We have all reviewed the ethics review guidelines and ensured that our paper conforms to them.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] The statement of Theorem
I contains a full description of assumptions, which is further expounded upon before and after the theorem statement.
(b) Did you include complete proofs of all theoretical results? [Yes] The proof of Theorem is provided in Appendix
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] Yes, full specifications of all experiments are provided in Section 5|d Appendix and full, documented source code is provided to reproduce our results.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Yes, full specifications of all experiments are provided in Section 5 and Appendix 6 and full, documented source code is provided to reproduce our results.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] Every numerical measurement in Tables contains confidence intervals
and
(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] Full specifications of computing resources are provided in 6
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] Yes, the only existing assets we used were publicly available datasets, which we cited in Section ??
(b) Did you mention the license of the assets? [Yes] We explicitly mention the licenses in
Section 5
14

---

(c) Did you include any new assets either in the supplemental material or as URL? [Yes] Yes, the only new assets created are in the form of code. which is entirely submitted in the supplemental material
(d) Did you discuss whether and how consent obtained from people whose data you' 're using/curating? [Yes] Yes, both datasets we use are publicly available and we mention the licenses in Section[31
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] The two datasets are the MNIST dataset and mathematical dataset; neither have any personally identifiable information offensive content.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] We did not use crowdsourcing or conduct research with human subjects.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] We did research with human subjects.
crowdsourcing conduct
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] We did not use crowdsourcing or conduct research with human subjects.
15


Reviews:
[{"review_id": "aeU-Cm_J1H4", "reviewer": "Reviewer_AzdZ", "summary": "The paper \"MABSplit: Faster Forest Training Using Multi-Armed Bandits\" proposes to estimate the performance of the splits during DT induction instead of evaluating them exactly. To do so, it views the splitting procedure as a multi-armed bandit problem which enables confidence bounds for each split that in-turn can be used to eliminate unpromising features \"early on\" by evaluating them only on a small subset of data points.", "questions": "1) You keep referring to a linear runtime for the exact split computation and I think I understand how you mean this, but please clarify the following for me: A very naive solution of finding the exact split is to iterate over all feature / split pairs (of which there are at most $Nm$ where $m$ is the number of features) and then to iterate over all data points to compute the probabilities $p_{L,k}$ and $p_{R,k}$ . A more evolved approach (which is implemented in most frameworks) would first sort the data points in $\\mathcal O(dN \\log N)$ and then perform two linear scans in which the statistics for the left and the right node are updated. Last, we can perform binning of the feature values into histograms which then requires a linear scan through the data. The exact procedure and runtime depends on the binning method. Assuming one feature ($m=1$) we have:\n\t1) The very naive approach has $\\mathcal O(N^2)$ runtime. \n\t2) The standard approach has $\\mathcal O(N \\log N + 2N) = \\mathcal O(N \\log N)$ runtime\n\t3) The binning method has $\\mathcal O(N)$ plus some additional overhead for the exact binning method.\n\t4) You refer to \"linear runtime\" to the linear scan in binning and not the linear scan in the \"standard approach\". This is confusing because you basically always talk about binning, but then mention sorting in line 306 (in the conclusion).\n2) You claim that MABSplit has a (sub-)linear runtime and I understand your remark under Theorem 1. However, just to clarify: The worst case runtime can still be $\\mathcal O(N^2)$ when we have $|\\mathcal F| \\cdot |\\mathcal T_f|  \\approx N$, correct? ", "limitations": "The expected runtime is analysed, but there is no worst-case runtime presented (see my question). Personally, this would improve the paper, but I don't think it absolutely necessary for acceptance.\nThe experimental evaluation is limited in a sense that they use a simple, non-optimized baseline. However, this is explicitly stated and makes sense in the context of the paper. \n", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper has a solid theoretical background and a novel algorithmic contribution, but lacks a thorough experimental evaluation. \n- [+] Novel and non-trivial extension of the node-splitting in DTs\n- [+] Solid theoretical work\n- [+] Solid literature review \n- [-] Experimental evaluation can be extended\n- [-] Wording of the paper is sometimes unclear.\n\n# Detailed Review\nI  like the idea and find it really interesting. I do not think I came across such a combination of bandit learning and DT induction yet and as such I find it a valuable contribution. While the authors do not explicitly motivate their work, the benefit should be clear to the reader. The related work section is solid, although I was a bit confused that XGBoost/LightGBM/CatBoost are not mentioned explicitly, although they are cited multiple times in the paper [12,24] . Section 2 and the first part of section 3 were also easy to follow in my opinion. Starting with Algorithm 1 it gets a bit troublesome. To me, the runtime of the proposed method is somewhat unclear. The authors give a theorem with the expected runtime, however, there is no worst-case runtime? I think the worst-case runtime is at-least also quadratic which means that for certain use-cases the proposed method is worse than the standard approach implemented in many frameworks (see my question below). Additionally, the  authors refer to a \"linear\" runtime multiple times in the paper, but I don't know exactly what they mean by this. Last, I find the experimental evaluation weak. It makes perfect sense to compare the algorithmic contribution to a base-line implementation, although implementing MABSplit into Weka or Scikit-learn would certainly improve the paper. However, the method is practically only evaluated on synthetic data and MNSIT. While using synthetic data is very important to isolate certain effects (e.g. the effect of the number and type of features is not discussed at all in the paper), some real-world experiments are also important. Last, and more crucial to me, the authors do not compare their approach against existing methods. More specifically, they do not compare it against the estimations used by Hoeffding's Trees [13,30] or the F-Forest [16] although these seem to be the only to similar methods available. I think a comparison here is urgently required. \n\n## Things to improve if the paper is rejected\n- Please refine what you mean by \"linear runtime\" throughout the paper. It would probably best to just give some pseudo-code of the exact split induction (with or without binning) to which you compare against. If space allows put that directly in the paper, otherwise use the appendix. \n- Point out the worst-case runtimes and the expected runtime of your method and related work. It should be clear that you win in terms of expected runtime and have better empirical results than the standard that is implemented in Scikit-learn/Weka etc.\n- Compare against Hoeffding Trees and/or F-Forest. As you write, these methods are very related so that you cannot ignore them in your evaluation\n- Add more (real-world) datasets. Personally, I think its fine to either go for classification or regression to simplify the analysis, but then use more datasets with varying amount of features and feature types. ", "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": "T87Vk3O0wCh", "reviewer": "Reviewer_wtDT", "summary": "In this paper, they proposed a MAB application for tree-based learning methods. Finding the best split takes O(n log(n)) time for a fixed feature, where n is the number of training instances. Their proposed algorithm, MABSplit, estimates the best split by drawing n' < n independent examples. MABSplit works as follows;\n1. Define the feasible set as the set of pairs of features and thresholds.\n2. While the size of the feasible set is greater than 1:\n    a. Draw a batch sample from training instances.\n    b. Shrink the feasible set.\nThey evaluated the computational complexity and verified the effectiveness of their algorithm by experiment.", "questions": "- Correctness of algorithm 1 (please see the details at limitations part).", "limitations": "I have some concerns about the correctness of the paper. Estimating entropy or gini index via sampling can be only done approximately. In particular, the entropy changes significantly at both ends (0 and 1), and the gradient is infinitely large there. So, it would need a careful analysis to employ Hoeffding bounds and others (e.g., case analysis). Furthermore, to ensure the correctness of algorithm 1, it would need an assumption about the gap between gains of the best one and others. ", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- a new application of bandit techniques to decision tree learning\n\n\nWeakness:\n- sone more explanation is necessary for the correctness of the algorithm", "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": "No2V_yNfdMT", "reviewer": "Reviewer_4wQQ", "summary": "The algorithm considers the selection of decision stumps using bandit algorithms. The decision stumps are used in algorithm such as random forest, extremely randomized forests, or random patches. The proposed method allows for a faster exclusion of candidate stumps that are not looking promising after a smaller number of evaluations (using Gini impurity or entropy).  Theoretical results offer some guarantees on the computational complexity. Empirical evaluation on the MNIST dataset show that the proposed selection technique results in much faster tree algorithms.  \n", "questions": "Framing the proposed method as a bandit algorithm seems a bit misleading, since all candidate stumps are evaluated. There is some connection with the arm elimination, but the differences in the setup should be perhaps better clarified.  \n", "limitations": "As mentioned above, the proposed technique might be more difficult to implement/optimize effiently.\n", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Reducing the set of candidate stumps using statistical measures is natural. I am not aware of previous work published with similar effect, but I would not be surprised if it has been attempted before. The theoretical guarantees seem fairly straightforward.\n\nThe empirical results are fairly impressive. It would have been useful to replicate the results on different datasets.\n\nThe experiments use reimplemented variants of the baseline algorithms. I understand the authors' argument for this choice, nevertheless, it should be pointed out that the full evaluation of stumps makes the optimizations present in publicly available implementations much easier. These optimization techniques might not be possible (or more difficult) for the selection technique proposed in the paper. Therefore, it would have been useful to provide the walk clock time comparisons with the publicly available implementations as well.  \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": "JkOZpnnj2g", "reviewer": "Reviewer_PuUT", "summary": "In the paper \"MABSplit: Faster Forest Training Using Multi-Armed Bandits\", a splitting criterion for fitting decision trees is proposed based on multi-armed bandits as to improve training efficiency, i.e., the time to train an entire random forest. To this end tuples of features and thresholds are each considered an arm and pulled for an instance to build histograms. Thereby, a sublinear runtime complexity (wrt. to the number of instances) can be achieved instead of linear runtime.", "questions": "* How does MABSplit perform across various datasets?\n* Why was only an artificial dataset used for regression?\n* What are limitations of MABSplit?\n* What are potential drawbacks of MABSplit?\n* Why does the performance for ExtraTrees in Table 2 degrade that much?\n", "limitations": "Limitations are not discussed in the paper. Thus, it is not clear what the strengths and the weaknesses of the approach are.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\nThe problem addressed by the paper is an important one, especially with sustainability and the climate crisis in mind. Working towards more efficient algorithms reduces energy consumption but also makes the usage of RF even more responsive in the sense that models can be obtained more quickly.\n\nTo the best of my knowledge, while there are various works on different split criterions for decision trees, the approach of this paper is novel and presents an original idea.\n\nOverall the paper is well structured and easy to read. However, I cannot induce the schema according to which the tables were colored and there is no explanation on that. Moreover there are still a few grammatical mistakes, e.g., l.22 \"is then be aggregated\", l.45 + l.241 \"O(n) computation\" -> computations, l. 112 the sentence is not complete, l.116 \"a M\" -> an M, l.224 \"data point\" -> data points. Furthermore sklearn's true name is scikit-learn.\n\n## Weaknesses\n\nWhile the general idea is quite interesting and the tackled problem is an important one, the paper falls short in terms of the scope of contribution. The theoretical contributions are relatively straightforward and the empirical study is quite limited. Although different variants of random forests are compared, only a single dataset (for a single split) for classification and a single artificial dataset for regression is used to benchmark and compare the proposed method with baselines. While this is already a good indicator that the method works indeed as intended, a more indepth evaluation of the proposed method is required to draw conclusions on a broader scale: How does MABSplit perform across various dataset sizes? For most tabular datasets MNIST already is comparably large, although for way smaller datasets there is not really a need for speeding up random forests. Anyways it would still be important to see how MABSplit compares for such smaller datasets. Then, the authors stated repeatedly that MNIST is only a small dataset. So, the question is how does it compare for datasets larger than MNIST? Does it scale as well as expected? For regression tasks the same arguments hold. Additionally, it is unclear why an artificial dataset was generated instead of using real-world data, e.g., from OpenML?\n\nThe result descriptions are quite descriptive without any more indepth explanations. The performance degradation in Table 2 was not addressed at all. How come that the performs degrades that much for ExtraTrees?\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": {}}]

Author rebuttal:

Decision: Accept