Near-Optimal Decision Trees in a SPLIT Second
Authors: Varun Babbar
Hayden McTavish
Cynthia Rudin
Margo Seltzer
Venue: ICML 2025 oral (2025)
Keywords: Decision Tree Optimization
Interpretable Machine Learning
Discrete Optimization
Primary area: social_aspects->accountability_transparency_and_interpretability
TL;DR: We find well performing sparse trees, dramatically improving scalability while maintaining SOTA accuracy.

Abstract: Decision tree optimization is fundamental to interpretable machine learning. The most popular approach is to greedily search for the best feature at every decision point, which is fast but provably suboptimal. Recent approaches find the global optimum using branch and bound with dynamic programming, showing substantial improvements in accuracy and sparsity at great cost to scalability. An ideal solution would have the accuracy of an optimal method and the scalability of a greedy method. We introduce a family of algorithms called SPLIT (SParse Lookahead for Interpretable Trees) that moves us significantly forward in achieving this ideal balance. We demonstrate that not all sub-problems need to be solved to optimality to find high quality trees; greediness suffices near the leaves. Since each depth adds an exponential number of possible trees, this change makes our algorithms orders of magnitude faster than existing optimal methods, with negligible loss in performance. We extend this algorithm to allow scalable computation of sets of near-optimal trees (i.e., the Rashomon set).

Near-Optimal Decision Trees in a SPLIT Second
Varun Babbar Hayden McTavish
Cynthia Rudin
Margo Seltzer'
Abstract
X
Greedy
X
Objective: 0.174
Decision tree optimization is fundamental in- terpretable machine learning. The most popular approach is greedily search for the best feature at every decision point, which is fast but provably suboptimal. Recent approaches find the global optimum using branch and bound with dynamic programming, showing substantial improvements in accuracy and sparsity at great cost to scala- bility. An ideal solution would have the accu- racy of an optimal method and the scalability of greedy method. We introduce family of algo- rithms called SPLIT (SParse Lookahead for In- terpretable Trees) that moves us significantly for- ward in achieving this ideal balance. We demon- strate that not all sub-prot sub-problems need be solved optimality to find high quality trees; greediness suffices near the leaves. Since each depth adds an exponential number of possible trees, this change makes our algorithms orders of magnitude faster than existing optimal methods, with negligible loss in performance. We extend this algorithm to allow scalable computation of sets of near-optimal trees (i.e., the Rashomon set).
Runtime: 0.02s
Xaa
X14
Objective
LicketySPLIT (ours)
Optimal
Objective: 0.143
Objective: 0. 042
X
Runtime: 1.01s
X
Runtime: -600s
X
X
X
Runtime
Figure 1. An illustration of the power of our optimization algo- rithm. We train 3 decision trees on the Bike dataset, with the aim of predicting bike rentals Washington DC in given time period. greedy tree fast but suboptimal. An optimal tree well performing but very slow. Our algorithm strikes the perfect balance, providing well performing trees a SPLIT second, orders of magnitude faster than optimal approaches in literature.
Optimizing the performance of decision trees while preserv- ing their simplicity presents significant challenge. Tradi- tional greedy methods scale lincarly with both dataset size and the number of features (Breiman, 1984; Quinlan, 2014).
However, these methods tend to yield suboptimal results, lacking general guarantees on either sparsity or accuracy. Recent advances in decision tree algorithms use dynamic programming techniques combined with branch-an and-boudd strategies, offering solutions that faster than brute-force approaches and provably optimal (Lin al., 2020; Aglin et al., 2020; Demirović et al., 2022; McTavish et al., 2022). In fact. Demirović et al. (2022) and van der Linden et al. (2024) reveal an average gap of 1-2 percentage points be- tween greedy and optimal trees, with Demirović et al. (2022) showing that some datasets can exhibit gaps as large as 10 percentage points. These algorithms struggle to scale to datasets with hundreds or thousands of features to deeper trees. It seems that we should return to greedy methods for larger-scale problems, but this would come at a loss of performance. Ideally, we should leverage greed only when it does not significantly deviate from optimality and use dynamic programming otherwise. Dynamic programming
1. Introduction
Decision tree optimization is core to interpretable machine learning (Rudin et al., 2022). Simple decision trees present the entire model reasoning process transparently, directly allowing faithful interpretations of the model (Arrieta al., 2020). This helps users choose whether trust the model and to critically examine any perceived flaws.
Equal contribution 'Department of Computer Science, Duke University, Durham, USA 'Department of Computer Science, University of British Columbia, Vancouver, Canada. Corre- spondence to: Varun <varun, babbar Sabbar@ddue.edus: Hayden <hay- nn..mttavishdduke.e....
Proceedings of the nd International Conference on Machine Learning. Vancouver, Canada. PMLR 267, 2025, Copyright 2025 by the author(s).
Code for algorithms and experiments be found at https:/ / / thub.
ICMI.

---

Near-Optimal Decision Trees in SPLIT Second
approaches build trees recursively, downward from the root.
sparse decision tree provide succinct individual expla- nations. However, finding deep, sparse trees with existing methods can be computationally infeasible. We bridge this gap our algorithms are capable of finding sparse trees without constraining them to be shallow.
Problems farther from the root contain fewer samples and produce fewer splits. As we show, greedy splits near the root sacrifice performance, while greedy splits near the leaves produce performance close to the optimal. This sug- gests that we can tolerate less precision on problems close to leaves than on problems closer to the root - and that full optimization on those problems closer the leaves yields only marginal returns relative to greedy, since we only have few splits remaining. This has enormous implications, since the number of candidate trees increases exponentially with increases in depth; using greedy splitting closer to the leaves of the tree massively reduces the search space.
Greedy Decision Trees A long line of work explores greedy algorithms such CART (Breiman, 1984) and C4.5 (Quinlan, 2014). These methods first define heuristic fea- ture quality metric such as the Gini impurity score (Breiman, 1984) or the information gain (Quinlan, 2014) rather than choosing a global objective function. At every decision node, the feature with the highest quality is chosen as the splitting feature. This process is repeated until termination criteria is reached. One such criteria often used is the mini- mum support of each leaf. Trees can then be postprocessed with pruning methods.
We leverage this observation to construct SPLIT (SParse Lookahead for Interpretable Trees), family of decision tree algorithms that are over 100x faster than state of the art optimal decision tree algorithms, with negligible sacrifice in performance. They can also be tuned to user-defined level of sparsity. Instead of searching through the entire space of decision trees up to a given depth, our algorithm performs dynamic programming with branch and bound up to only a shallow "lookahead" depth, conditioned on all splits henceforth being chosen greedily.
Branch and Bound Optimization Among the many methods for globally optimizing trees, Branch-and-bound approaches with dynamic programming are state of the art for scalability, because they exploit the structure of decision trees (Costa & Pedreira, 2023; Lin et al., 2020; Demirović et al., 2022; McTavish et al., 2022: Aglin et al., 2020). While many other methods exist for optimizing trees, such as MIP solvers (Bertsimas & Dunn, 2017: Verwer & Zhang, 2019), we focus our discussion and comparison of globally optimal decision tree methods on the currently fastest types of ap- proaches- dynamic programming with branch and bound (DPBnB). These approaches search through the space of decision trees while tracking lower and upper bounds of the overall objective at each split to reduce the search space. They can find optimal trees on medium-sized datasets with tens of features and shallow maximum tree depths (Sullivan et al., 2024; Aglin et al., 2020; Lin et al., 2020; Demirović et al., 2022). Aglin et al. (2020) uses DPBnB method with advanced caching techniques to find optimal decision trees, though it does not explicitly optimize for sparsity. In contrast, Lin et al. (2020); Hu et al. (2019) use a DPBnB approach to find tree that optimizes a weighted combina- tion of empirical risk and sparsity, defined by the number of leaves in the tree. McTavish et al. (2022) further enhances this approach by incorporating smart guessing strategies to construct tighter lower bounds for DPBnB, resulting in computational speedups. Demirović et al. (2022) extends the work of Aglin et al. (2020) by focusing on finding the optimal tree with a hard constraint on the number of per- missible nodes, using advanced caching techniques and an optimized depth-2 decision tree solver. Mazumder al. (2022) addresses continuous features by defining lower and upper bounds based on quantiles of feature distributions. However, their method is applicable only to shallow optimal trees with depth I 3, limiting its utility in scenarios with higher-order feature interactions.
Our contributions are as follows.
We develop a family of decision tree algorithms that scale with the dataset size and number of features comparably to standard greedy algorithms but produce trees that are as accurate and sparse as optimal ones (e.g., Lin et al., 2020).
We extend our decision tree algorithms to allow scalable, accurate approximations of the Rashomon set of decision trees (Breiman, 2001; Xin et al., 2022).
We theoretically prove that our algorithms scale exponen- tially faster in the number of features than optimal decision tree methods and are capable of performing arbitrarily better than purely greedy approach.
2. Related Work
We are interested in accurate, interpretable decision tree classifiers that we can find efficiently. We discuss these three goals as they pertain to existing work.
Consistent with recommendations from Rudin et al. (2022); Costa & Pedreira (2023), we emphasize sparsity, expressed in terms of the number of leaves, as the primary mechanism for tree interpretabiliiy. Sparsity has a strong correlation with user comprehension (Piltaver et al., 2016). Zhou et al. (2018) fit regression model to user-reported interpretability for decision trees, also finding that trees with fewer leaves were more interpretable. They also found that deep, sparse trees were more interpretable than shallow trees with the same sparsity. Izza et al. (2022) provides way to use
2

---

Near-Optimal Decision Trees in SPLIT Second
Lookahead Trees Some older approaches greedy de- cision tree optimization consider multiple levels of splits before selecting the best split at a given iteration (Norton, 1989). That is, unlike the other greedy approaches, these approaches do not pick the split that optimizes a heuristic immediately, Instead, they pick a split that sets up the best possible heuristic value on the following split.
to optimize for sparsity.
Recent work by Chaouki et al. (2024) devises a Monte Carlo Tree Search algorithm using Thompson sampling to enable online, adaptive learning of sparse decision trees. We show that our method achieves superior performance and sparsity on all datasets tested.
These approaches still focus on locally optimizing a heuris- tic measure that is not necessarily aligned with a global objective. By contrast, our method selects splits to directly optimize the sparse misclassification rate of the final tree. We globally optimize the search up to the specified looka- head depth, switching to heuristics only when deciding splits past our lookahead depth. In so doing, our method largely avoids the pathology noted in Murthy & Salzberg (1995), who note cases where their own lookahead approach results in a substantially worse tree than one constructed with standard greedy approach. For our method, it is provably impossible for a fully greedy entropy-based method with the same constraints as our approach to achieve a better training set objective than our approach. (See Theorem A.1)
3. Preliminaries
We consider a typical supervised machine learning setup, with a dataset D = {(x;, b sampled from a distribu- tion D, where x, E {0, 1] is a binary feature vector and YI E {0, 1] is a binary label.' Let F be the set of features. Define D(J) as the subset of D consisting of all samples where feature f E F 1 (and D(f) as the subset where feature I is 0). Let D+ and D denote the set of examples with positive and negative labels, respectively.
Node specific notation Let Dr be the support set of node t in tree (i.c., the set of training examples assigned to this node); we call each D, subproblem. Let ft E F be the feature we split on at l. Let De(Jt) and (Ja) be the support sets of the children t. Unless stated otherwise, a greedy split at node chooses the feature f that maximizes the information gain, which equivalent to solving:
Other Hybrid Methods Several other approaches are compatible with branch and bound techniques. Blanc et al. (2024) seek to bridge the gap between greedy and optimal decision trees by selecting a fixed subset of the top k feature splits for each sub-probles poobleroblmmm.... However, this framework does not explicitly account for sparsity. Further, the method is limited by using global setting for search precision: the approach considers the same number of candidate splits at each subproblem. As we show in our experiments, there is merit to tailoring the level of search precision to parts of the search space where it is most needed. The Blossom algo- rithm (Demirović et al., 2023) traverses a branch and bound dependency graph structure while using greedy heuristics to guide the search order. Relative to our approach, this al- gorithm optimizes from the bottom up, starting with greedy splits at each level, then optimizing the splits furthest from the root first. This choice guarantees eventual optimality while giving anytime behavior, but misses out leveraging the property motivating this work- that greedy splits are most detrimental near the top of the tree. Like the approach of Blanc et al. (2024), Blossom also does not account for sparsity.
ID((F), ( (IDE(AI) |Di(F), IDil (D(((F))
(IDF (F)
ft min JEF
и
H [De]
(IDi())
with entropy H(p) = ----ploog (1-p) p) log(1 - p).
Tree specific notation We now briefly discuss sparse greedy and optimal trees. We define (D, d, A) to be a decision tree of depth at most trained greedily on D with sparsity penalty A. Intuitively, this sparse greedy algorithm will make split at node only when the gain in overall accuracy is greater than X. Algorithm 4 in the Appendix illustrates this procedure. Modern methods such as Lin et al. (2020); McTavish et al. (2022), on the other hand, find a tree T in the space of decision trees T that solves the following optimization problem:
L' = min (T,D,A) s.t. dTp S d TET
(1)
[D]
There are a few methods that use probabilistic search tech- niques to optimize trees. Sullivan et al. (2024) take a tree
min TET 1=1
(I((x));))) + AS(T)) s.t. depth(T) S d
N
Bayesian approach, finding the maximum-a-postert by optimizing over an AND/OR graph, akin to the graph used in earlier branch-and-bound methods like that of Lin et al. (2020). Although their method demonstrates strong performance, their experimental results reveal that is not responsive to ingly, we found in our experiments that the method struggles
where L(T, D, A) is the regularized loss of tree T on dataset (or data subset) D, S(T) is the number of leaves in T, {(T(x),)) y) is the loss incurred by T in its prediction on x
'The discussions and methods in this paper can trivially be extended multiclass problems; we focus our discussion and evaluation of the methodology on binary labels.
hyperparameters - accord-
3

---

Near-Optimal Decision Trees in SPLIT Second
(for this paper, we set l to be the 0-1 loss), and N is the global dataset size. As discussed in Section 2, the fastest contemporary methods solve this problem using a branch- and-bound approach (Costa & Pedreira, 2023; Lin et al., 2020; Demirović et al., 2022; McTaavis et al., 2022).
start min(ub, 22), since either L(D,, d', X) = ub, or the objective will be the sum of two other L calls, both of which must necessarily have cost at least A. These upper and lower bounds are then updated as we explore a graph structure containing these subproblems. Once these bounds have converged, and we know the value of L d', A) for the whole dataset D, we can extract the optimal tree by simply tracking the feature f that leads to the optimal score for D and then successively track the splits for the optimal value with respect to Df) and D(f), and so on.
Rashomon Sets Our work is motivated by the proper- ties of near-optimal decision trees and allows for scalable approximation of that set. Xin et al. (2022) define the Rashomon set, denoted by R(D,,, A, e, d), as the collection of all trees whose objective is within c of the minimum value in Equation Formally:
S R,D,,, d) = ET: & (DD,
Discretization Our algorithm will assume feature vectors to be binary, i.e., x; E {0, 1) Real-world datasets often have features that require discretization to fit our setting, While some methods preserve optimality (e.g.. splitting the mean between unique values in the training set), others such as bucketization (described and proven to be subopti- mal in Lin et al., 2020), binning into quantiles, and feature engineering reduce the search space at the cost of optimality. In our experiments, we use threshold guessing (McTavish et al., 2022), which sacrifices optimality with respect to a real-valued dataset but maintains theoretical and empirical guarantees relative to reference decision tree ensemble.
A depth (T) s d).
(2)
In Section 4, we use Rashomon sets to investigate properties of near-optimal trees.
Rashomon sets can be used for a range of downstream tasks (Rudin et al., 2024); one crucial task the measurement of variable importance over a set of near-optimal models instead of only for single model (Donnelly et al., 2023; Fisher et al., 2019). Reliable variable importance measures in this setting rely on minimal feature selection prior to computing the Rashomon set and minimal constraints on the tree's depth to allow high-order interactions. Our approach can be used to accelerate the computation of Rashomon set, supporting the feasibility of these approaches.
4. Algorithm Motivation
A key motivating property of SPLIT is that we can find high quality trees even when splitting greedily far from the root of the tree. To support this intuition, empirically investigate how frequently near optimal trees behave greedily far from the root. To do so, we first generate the Rashomon set of decision trees for various values of sparsity penalty À and Rashomon bound e. Let T E R(D, X, e, d) be a tree in the Rashomon set, and let n E T be any node in T. Then, we compute the fraction of all nodes at a given level & S d (where level 0 corresponds to the root) that were greedy (by which we mean that the split at this node in the tree is optimal with respect to information gain). This corresponds to the following proportion:
Branch and Bound Given a depth budget d, branch and bound with a sparsity penalty (Lin et al., 2020; McTavish et al., 2022) finds the optimal loss L- (D, d, A) that mini- mizes Equation! 1.
The key insight behind branch and bound is that the opti- mal solution for dataset D at depth d' has a dependency on the optimal solution for datasets D()) and D(J) at depth d' 1, for each f E F. Starting from the root, branch and bound algorithms consider different candidate features, f, on which to split in the process of determining the ob- jective. As candidates are considered, we identify the sub- problems we encounter by the subset of data they relate to and their remaining depth. We track current upper and lower bounds of subproblems in order to prune parts of the search space as we explore it. In particular, if our lower bounds on L* (Dr(Ji), d' 1, A) and L (D+ d' - 1, X) sum larger value than the sum of upper bounds on L' (D)(()))) d' 1, and L (D)) d' - 1, A), for exam- ple, then we have proven that fi is not the minimizing split for dataset D.
Σ
Σ
In is greedy A level(n) E]
TER(D. nET
(3)
Σ Σ 1[leve((n) = E]
TER(D.Ac.d)ne) nET
Figure 2 shows the results of this investigation for 6 dif- ferent datasets for different values of c and A. We note that there is a general increase in percentage of greedy splits as one goes deeper in the tree.
L(D;, d', >) can always start with an upper bound of ub- = + min (LD pt
A universal lower bound is X. To
[ [P.T]
get a tighter lower bound, if d' > 0, the lower bound can
4

---

Near- Star-Optimal Decision Trees in SPLIT Second
Level 0
Level
Lovel 2
Lovel 3
set F, first solve the following recursive equation:
covertype
0.83
0..02
C(D, ,',
0.32
D (T, d'
D
netherlands
6.00
3e-3
1e-3
min
A
N
(D(,,
min fEF
5.3
Proportion of Greedy Splits
compas
0.88
if di
D
A D+
0.83
min
A
0.5
8.5
1, (c(D()), - + f (D((),
0.375
min
0.02
if d di.
2.5
5.0
75 23
5.0
74:25
5.0
74.25
5.5
75
(4)
00.00
Where N is the size of the dataset the root. We can con-
0.21
Se-2
14-3
le-3
Algorithm got.bbonddsD, di, d. d', N) lb, ub Require: D, dr, d, d', N (support, lookahead depth, cur- rent search depth, maximum search depth, size of full dataset in GOSDT call)
0.29
0,000
0.002
3.72
36-1 16-3 16.13
if d' di then
Figure heatmap of the proportion of splits of trees in the Rashomon set that are greedy, stratified by level, for different (X, e) combinations. Only 4 levels shown the 5th level corresponds to the leaf. The greyed out regions in the bottom right a plot represent (A, c) for which the Rashomon set did approach
Tg Greedy d di, (Find greedy tree rooted at D (Alg 4 in the Appendix))
3:
S(Tg) = # Leaves in T
4:
+ N Emnyen 1ly + Tz(x)) [ AS(T,)
5: lb - a
not contain any trees of that depth. Generally, leaves, the proportion of splits appearing in e-optimal trees become increasingly greedy. This especially noticcable for the Netherlands, Covertype, and COMPAS datasets.
ub + a (subproblem solved because ub lb}
else {use basic initial bounds]
lb 2A
ub + x x min 1 D*1
10: end if
11: return lb,ub [Return Lower and Upper Bounds}
Additional motivating empirical results for using greedy splits far from the root of the tree are provided in Appendix A.2.
strain the search space to include only greedy trees past the lookahead depth by modifying the lower and upper bounds used in branch and bound (see Algorithm 1). In particular, sub-problem nodes initialized at depths up to the lookahead depth are assigned initial lower and upper bounds equivalent to that in GOSDT (Lin et al., 2020) (see Section 2). At the lookahead depth, however, the lower and upper bounds for subproblem are fixed be the loss of greedy subtree trained on that subproblem. After these bound assignments, algorithm uses the GOSDT algorithm with these new bounds to solve Equation 4 this is summarized by Lines 1-2 in Algorithm 2. We defer more details of the GOSDT algorithm to Section A.12 in the Appendix.
5. A Algorithm Details
5.1. SParse Lookahead for Interpretable Trees (SPLIT)
We now formalize our main algorithm, SPLIT, which takes as input a lookahead depth parameter. This is the depth up to which search algorithm optimizes over all combinations of feature splits, conditioned on splits beyond this depth behaving greedily. Our algorithm exploits the fact that sub- problems closer to the leaves exhibit smaller optimality gaps than those at the root, providing a mechanism to trade off among runtime, accuracy, and sparsity.
Postprocessing with Optimal Subtrees Once we have solved Equation 4, we do not need to use greedy sub-trees past the lookahead depth. We can improve our approach by
Formulating the optimization problem Concretely, for a given depth budget lookahead depth d, < d, and feature
5

---

Near-Optimal Decision Trees in SPLIT Second
Algorithm 2 SPLIT(E, D, X, de, d)
Algorithm 3 LicketySPLITTC, D, A, d)
Require: l. A, di, d d floss function, samples, regular- izer, lookahead depth, depth budget, postprocess flag)
Require: D, X, d (loss function, samples, regularizer,
full depth}
1: ModifiedGOSDT = GOSDT reconfigured to use get bounds (Algorithm 1) whenever it encounters a new subproblem
Ulookahead SPLIT D, D, {Call SPLIT with lookahead depth 1 and no post-processing)
1: if [ookahead is not a leaf then
1: Mookahead = ModificdGOODD(( D, di) {Call Mod-
2: for child u E Muukaheea do
ifiedGOSDT with depth budget d:}
3: D(u) = =subproblem associated with u
A= X [D] p(() {Renormalize À for the subproblem in question)
2: if p then {Fill in the leaves of this prefix}
4:
3: for leaf ltookabead do
4: dy depth of leaf
5:
t. =LicketySPLITTC, D(u), Aus 1)
5:
(uu)= subproblem associated with u
6: Replace u. with subtree tu
6: Aa= ||]
[ (Renormalize for the subproblem
7: end for
in }
8: end if
7:
tu = GOSDT D(u), d- Au) {Find the optimal
9: return tjookahead
subtree for {
8:
if ln is not leaf then
9:
Replace leaf with sub-tree tu
5.3. RESPLIT: Rashomon set Estimation with SPLIT
10: end if
11:
end for
At the cutting edge of compute requirements for decision tree optimization is the computation of Rashomon sets of decision trees. Xin et al. (2022) compute Rashomon set of all near-optimal trees, based on the GOSDT algorithm (Lin et al., 2020). This task generates an extraordinary num- ber of trees and has high memory and runtime costs. To make this tractable, Xin et al. (2022) leverage depth con- straints and feature selection from prior work to reduce the depth and set of features considered (McTavvish al., 2022). While necessary for scalability, this can prevent exploration of near-optimal models across all features or at greater de- cision tree depths. Both factors are relevant for work on variable importance based on Rashomon sets (Fisher et al., 2019; Dong & Rudin, 2020; Donnelly et al., 2023). We leverage SPLIT as way to dramatically improve scalability of Rashomon set computation, reliably approximating the full Rashomon set and allowing feasible exploration while relaxing removing depth and feature constraints.
12:
end if
13:
return tlookahead
replacing these subtrees with fully optimal decision trees. Lines 3-9 in Algorithm 2 illustrate this. Thus, the perfor- mance of the lookahead tree with the aforementioned greedy subtrees is just an upper bound on the objective of the tree method ultimately finds.
Note that the renormalization in line 6 of Algorithm 2 en- sures that the X penalty stays proportional to the penalty for each misclassified point. Our objective (Equation 1) assigns a N penalty for each misclassification, where N the size of the full dataset with which GOSDT was called. If the original dataset is D, then when call GOSDT on any descendent subproblem Duu), our penalty per misclassifi-
cation goes up by a factor of [D]
T We need to scale X
Our algorithm. RESPLIT, is described in Appendix A. 10; it first leverages SPLIT as a subroutine to obtain a set of prefix trees such that completing them greedily up to the depth budget would result in an e approximation of the optimal solution Equation 4. At each leaf of each prefix tree, calls TreeFARMS (Xin et al., 2022) to find a large set of shallow subtrees that are at least as good as being greedy, yielding an approximate Rashomon set computed much faster than state of the art. We also show a novel indexing mechanism to query RESPLIT trees in Appendix A.11.
appropriately to stay proportional to the original dataset D.
5.2. LicketySPLIT: Polynomial-time SPLIT
We present a polynomial-timg variant of SPLIT, called Lick- etySPLIT, in Algorithm 3. This method works by recur- sively applying SPLIT with lookahead depth 1. That is, we first find the optimal initial split for the dataset, given that we are fully greedy henceforth. Then, during postprocess- ing, instead of doing what SPLIT would do running fully optimal decision tree algorithm on the root's left and right subproblems we run LicketySPLIT recursively on these two subproblems. We stop considering further calls to LicketySPLIT for a subproblem if SPLIT returns a leaf instead of making splits (either due to the depth limit or X).
6. Theoretical Analysis of Runtime and Optimality
We present theoretical results establishing the performance and scalability of our algorithms. All proofs, including
6

---

Near-Optimal Decision Trees in SPLIT Second
LicketySPLIT (ours)
SPLIT (ours)
gosdt
Bike
Adult
Netherlands
102
10a
102
104
10
10
0.04
Training Time
100
10
100
0.03
0.2
0.3
0.20
0.25
0.30
0.35
0.40
Heloc
Compas
Covertype
0.02
102
100
10a
10
0.01
104
10 1
100
100
0.30
0.35
0.35
0.40
0.25
0.30
0.35
Regularized Test Loss
Figure 3. Regularized test loss vs training time (in seconds) for GOSDT (McTavish et al., 2022) vs our algorithms. The size of the points indicates the number leaves in the resulting tree. Both SPLIT LicketySPLIT are much faster for most values sparsity penalty X, with the only potential slowdown being in the sub-second regime due to overhead costs.
additional lemmas not described below, in Appendix Section A.8. Even without the speedups discussed in Sec- tion 5.2, Algorithm 2 is quite scalable. Theorem 6.1 shows the asymptotic amalysis of the algorithm, with and without caching. Note that the default behaviour of Algorithm 2 is to cache repeated sub-problems.
conditions Theorem 6.1 and with caching repeated sub- problems, Algorithm 2 saves factor of O d-1 in runtime relative to globally optimal approaches (e.g.. GOSDT).
Theorem 6.4 describes the runtime complexity of our Lick- etySPLIT method from Section 5.2, showing that can be even faster than Algorithm 2 (indeed, achieving low-order polynomial runtime).
Theorem 6.1 (Runtime Complexity of SPLIT). For dataset D with & features and n samples, depth constraint d such that d & k, and lookahead depth 0 S di d, Al- gorithm 2 has runtime Onn(d - di di)kdt+1 + nkd-d:). If we cache repeated subproblems, the runtime reduces to o níd-d, "." 122-2-0
Theorem 6.4 (Runtime Complexity of LicketySPLIT), For dataset D with l features and samples, and for depth constraint d, Algorithm 3 has runtime dn
del
This algorithm is linear in sample size and, because di < d and di < d, is exponentially faster than globally optimal approach, which searches through (((k)dd) sub- problems in the worst case.
We can thus use Algorithm 3 to leverage recursive search while remaining comfortably polynomial. This a dramatic improvement to asymptotic scalability relative to globally optimal decision tree construction methods, which solve an NP-hard problem.
Corollaries 6.2 and 6.3 show that, compared to globally optimal approaches, we see substantial improvements in runtime when lookahead depth is around half the global search depth.
Theorem 6.5 (SPLIT Can be Arbitrarily Better than Greedy). For every >> and depth budget d, there ex- ists data distribution D and sample size for which, with high probability over random sample S ~ DD, Algorithm with di - greedy approach achieves accuracy at most 2 +
Corollary 6.2 (Optimal Lookahead Depth for Minimal Run- time). The optimal lookahead depth that minimizes the asymptotic runtime of Algorithm 2 di (d-1) for large k. regardless of whether subproblems cached.
d-1 achieves accuracy at least 1 1 but pure
Theorem 6.5 shows that Algorithm 2 can arbitrarily outper- form greedy methods in accuracy, even when we choose its minimum runtime configuration of d; 2
Corollary 6.3 (Runtime Savings of SPLIT Relative to Glob- ally Optimal Approaches). Asymptotically, under the same
d-1 We prove

---

Near-Optimal Decision Trees in SPLIT Second
similar claims for LicketySPLIT and RESPLIT in the appendix (see Theorems A.7 and A.6).
7.2. Characterising the Frontier of Test Loss, Sparsity, and Runtime
Figure 4 characterises the frontier of training time, sparsity, and test loss for several algorithms. Here, we vary hyper- parameters associated with each algorithm to produce trees of varying sparsity levels (where sparsity is the number of leaves). We see that there exists a frontier between test loss and sparsity, and different methods lie on different parts of the frontier. To maximize interpretability and aceuracy, we want tree to lie in the bottom left corner of the frontier, within the highlighted red rectangle. Out of all algorithms tested, ours consistently lie on the frontier and in the red rectangle. Alongside state of the art performance, our algo- rithms are often over 100x faster than their contemporaries. For more datasets, see Figure 5 in the Appendix.
7. Experiments
Our experiments provide an evaluation of decision trees, considering aspects of performance, interpretability, and training budget. To this end, our evaluation addresses the following questions:
1. How fast are SPLIT and LicketySPLIT compared to unmodified GOSDT?
2. Are SPLIT and LicketySPLIT able to produce trees that lie on the frontier of sparsity, test loss performance, and training time?
3. How good is the Rashomon set approximation pro- duced by RESPLIT?
7.3. Rashomon Set Approximation
We now show that RESPLIT enables fast, accurate approx- imation of the Rashomon set of near-optimal trees, while scaling much more favorably than of-h-aff method TreeFARMS (Xin al., 2022). We demonstrate that vari- able importance conclusions using RID (Donnelly al., 2023) remain almost identical under RESPLIT, relative to the full Rashomon set. That is, RESPLIT allows accurate summary statistics the full Rashomon set to be computed at greater depths and over more binary features while en- hancing scalability. Table 1 shows computation of RID with and without RESPLIT. RESPLIT enables 10 20x faster variable importance computation. Furthermore, the correlation between variable importances is very close to 1, suggesting that RESPLIT trees serve as good proxies for es- timating importances derived from the complete Rashomon set. Table also shows that most of the trees output by RESPLIT lie the true Rashomon set or very close to it.
For all experiments below we the depth budget of our algorithms to 5. The lookahead depth for Algorithm 2 is set to 2 since, from Corollary 6.2, this produces the lowest runtime for the chosen depth budget. We defer more details of our experimental setup and datasets to Appendix A.7.4. Appendix A.3 has additional evaluations of our methods.
7.1. How do our algorithms compare to GOSDT?
Our first experiments support the claim that our method is significantly faster than GOSDT whilst achieving similar regularized test losses. This is shown in Figure 3. Here, we vary the sparsity penalty, X, which is common input to all algorithms in this figure, and compute the regularized test objective from Equation I for each value of X. We set a timeout limit of 1200 seconds for GOSDT, after which it gives the best solution found so far. We note two regimes:
When all methods have lower regularized objective val- ues (left side of each plot), methods are orders of magnitude faster than GOSDT. For instance, the Bike dataset, SPLIT has training times of 100 seconds, while GOSDT runs for ~03 seconds. LickItySPLIT takes merely a second in most cases. This is the regime most relevant to our algorithms.
Dataset
Full (s)
RESPLIT (s)
COMPAS
152
18
1.0
Spambase
2659
154
0.930
Netherlands
4255
216
0.932
HELOC
5564
337
0.979
When the optimal objective is high and the tree is super- sparse (right side of each plot), SPLIT and Lickety- SPLIT have small overhead costs and can be slower, because we need train greedy tree for each sub- problem encountered at the lookahead depth in order to initialize bounds via Algorithm 1. However, in this regime, all methods already have runtimes of ~ sec- ond, so the extra overhead cost is insignificant. This is especially seen in the COMPAS and Netherlands datasets.
HIV
9273
388
0.959
Bike 14330
194
0.999
Table 1. Table summarizing the advantages of RESPLIT. The first 2 columns show the time taken to compute all bootstrapped Rashomon sets for the Rashomon Importance Distribution (RID) (Donnelly et al., 2023) with and without RESPLIT. # of boot- strapped datasets 10, À 0.02, 0.01, depth budget 5, lookahead depth 3. The last column shows the Pearson corrolation between variable importances computed by RID and RID RE- SPLIT. There is nearly perfect correlation seen in every case.
8

---

Near-Optimal Decision Trees in SPLIT Second
Test Loss vs Leaves for Different Decision Tree Algorithms
(ours)
greedy topk (dl8.5)
tsdt gosdt
maptree
LicketySPLIT (ours)
murtree
netherlands
bike
adult
0.40
Test Loss
0.4
0.225
0.35
0.200
0.2
0.30
100 MP
0.175
20
30
10
20
30
10
20
30
Number of Leaves
Number Leaves
Number Leaves
Test Loss vs Training Time for Models in the Red Box
0.32
0.19
Test Loss
0.20
0.18
0.30
0.15
0.17
10 10
10a
10-1
10
10a
10 10-1
10
10a
Training Time (s)
Training Time (s)
Training Time (s)
Figure 4. A comparison between the performance of our algorithms and competitors (depth budget 5, lookahead depth 2). The red box the upper plot illustrates the region containing sparse and accurate models. The lower plots show the test loss vs training time for models in the red box. SPLIT and LicketySPLITT consistently lie on the bottom left of the test loss-sparsity frontier, with runtimes orders of magnitude faster than many competitors. Our algorithms also offer the ideal compromise between runtime and loss. All metrics are averaged over 3 test-train splits.
Dataset
Precision
Precision (Slack .01)
cient decision tree and Rashomon set optimization.
Bike
0,974 (370/380)
1.000
COMPAS
1.000 (27/27)
1.000
Acknowledgements
HELOC
0.974 (528/542)
1.000
HIV
0.528 (243/460)
0.984
We acknowledge funding from the National Institutes of Health under 5R01-DA054994, the National Science Foun- dation under award NSF 2147061, and through the De- partment of Energy under grant DE-SC0023194. We thank Srikar Katta, Jon Donnelly, Zachery Boner, Yixiao Wang, and Zakk Heile for helpful discussions and feedback throughout this project.
Netherlands
0.911 (102/1
1.000
Spambase
0.597 (850/1422)
0.933
Table Proportion of RESPLIT Trees in the true Rashomon set (precision) and within most .01 loss of being in the set. Most of the trees output by RESPLIT end up being in the Rashomon set. Trees which not the Rashomon close to being in it. We employ the same parameters as Table 1.
almost always very
Impact Statement
8. Conclusion
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
We introduced SPLIT. LicketySPLIT, and RESPLIT, a novel family of decision tree optimization algorithms. At their core, these algorithms perform branch and bound search up lookahead depth, beyond which they switch to greedy splitting. Our experimental results show dramatic improve- ments in runtime compared to state of the art algorithms, with negligible loss in accuracy sparsity. RESPLIT also scalably finds set of near-optimal trees without adversely impacting downstream variable importance tasks. Future work could explore conditions under which subproblems exhibit large optimality gaps, offering new insights for effi-
References
Aglin, G., Nijssen, S., and Schaus, P. Learning optimal decision trees using caching branch-and-bound search. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 34, pp. 1146-3153, 2020.

---

Near-Optimal Decision Trees in SPLIT Second
Arrieta, A. B., Diaz-Rodríguez, N., Del Ser, J., Bennetot, A., Tabik, S., Barbado, A., García, S., Gil-López, S., Molina, D., Benjamins, R., et al. Explainable artificial intelli- gence (XAI): Concepts, taxonomies, opportunities and challenges toward responsible Al. Information Fusion, 58:82-115, 2020.
Dong, and Rudin, C. Exploring the cloud of variable im- portance for the set of all good models. Nature Machine Intelligence, 2(12):8 (11))810-824, 10-824, 2020.
Donnelly, J., Katta, S., Rudin, C., and Browne, E. P. The rashomon importance distribution: Getting RID of unsta- ble, single model-based variable importance. In Advances in Neural Information Processing Systems, 2023.
Balcan, M.-F. and Sharma, Learning accurate and inter- pretable decision trees. In Proceedings of the Fortieth Conference Uncertainty in Artificial Intelligence, UAI '24. JMLR.org, 2024.
Fanace-T. T, H. and Gama, J. Event labeling combining semble detectors and background knowledge. Progress in Artificial Intelligence, pp. 1-15, 2013. doi: 10.1007/ s 07488-013-0040-.
Bertsimas, D. and Dunn, J. Optimal classification trees. Machine Learning, 166:1039-10882 2017.
FICO.
equity line of credit (heloc) dataset. httpps:/ccommuityy com/// wawthaaaee-nacii--eeeeeeeee
Home
Blanc, G., Lange, J., and Tan, L.-Y. Top-down induction of decision trees: rigorous guarantees and inherent limita- tions. arXiv preprint 1rX.v:9911.073777 2019.
2018. FICO Explainable Machine Learning Challenge.
Fisher, A., Rudin, C., and Dominici, F. All models are wrong, but many are useful: Learning a variable's impor- tance by studying an entire class of prediction models simultaneously. Journal of Machine Learning Research, 20(177):1 81, 2019.
Blanc, G., Lange, J., Pabbaraju, C., Sullivan, C., Tan, L.- Y., and Tiwari, M. Harnessing the power of choices in decision tree learning. Advances in Neural Information Processing Systems, 36, 2024.
Breiman, L. Classification and regression trees. Routledge, 1984.
Hu, X., Rudin, C., and Seltzer, M. Optimal sparse decision trees. In Advances in Neural Information Processing Systems, volume 32, pp. 7265-7273, 2019.
Breiman, L. Statistical modeling: The two cultures (with comments and a rejoinder by the author). Statistical Science, 16(3):199-231, 2001.
Izza, Y., Ignatiev, A., and Marques- Silva, J. On tackling explanation redundancy in decision trees. Journal of Artificial Intelligence Research, 75:261-321, 2022.
Chaouki, A., Read, J., and Bifet, A. Online learning of decision trees with Thompson sampling. In Dasgupta, S., Mandt, S., and Li, (eds.), Proceedings of The 27th International Conference Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learn- ing Research, pp. 2944-2952. PMLR, 02-04 May 2024.
Lin, J., Zhong, C., Hu, D., Rudin, C., and Seltzer, M. Gen- eralized and scalable optimal sparse decision trees. In International Conference on Machine Learning, pp. 6150- 6160. PMLR, 2020.
Lóezi, L. Explicit and recursive estimates of the Lambert W function. arXiv 2008.06122. 2021.
Chatzigeorgiou, I. Bounds on the lambert function and their application to the outage analysis of user cooperation. IEEE Communications Letters, 17(8):1005-1508 August 2013.
Mazumder, R., Meng, X., and Wang. H. Quant-BnB: A scal- able branch-and-bou method for optimal decision trees with continuous features. In International Conference on Machine Learning, volume 162, pp. 15255-15277. PMLR, 17-23 Jul 2022.
Costa, V. G. and Pedreira, C. E. Recent advances in decision trees: An updated survey. Artificial Intelligence Review, 56(5):4765-4800, 2023.
McTavish, H., Zhong, C., Achermann, R., Karimalis, I., Chen, J., Rudin, C., and Seltzer, M. Fast sparse decision tree optimization via reference ensembles. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 9604 9613, 2022.
Demirović, E., Lukina, A., Hebrard, E., Chan, J., Bailey, J., Leckie, C., Ramamohanarao, K., and Stuckey, P. Murtree: Optimal decision trees via dynamic program- ming and search. Journal of Machine Learning Research, 23(26):1-47, 2022.
Murthy, S. and Salzberg, S. Lookahead and pathology in decision tree induction. In International Joint Conference on Artificial Intelligence, pp. 1025-1033, 1995.
Demirović, E., Hebrard, E., and Jean, L. Blossom: an anytime algorithm for computing optimal decision trees. In International Conference on Machine Learning, pp. 7533-7562, PMLR, 2023.
Norton, S. W. Generating better decision trees. In Interna- tional Joint Conference on Artificial Intelligence, 1989.
10

---

Near-Optimal Decision Trees in SPLIT Second
Piltaver, R., Luštrek, M., Gams, M., and Martinčić-Ipšié, S. What makes classification trees comprehensible? Expert Systems with Applications, 62:333-346, 2016.
Quinlan, R. C4.5: programs for machine learning. Else- vier, 2014.
Rudin, C., Chen, C., Chen, Z., Huang, H., Semenova, L., and Zhong, C. Interpretable machine learning: Funda- mental principles and 10 grand challenges. Statistics Surveys, 16:1-85, 2022.
Rudin, C., Zhong. C., Semenova, L., Seltzer, M., Parr, R., Liu, J., Katta, S., Donnelly, J., Chen, H., and Boner, Z. Amazing things come from having many good models. Proceedings of the International Conference Machine Learning, 2024.
Sullivan, C., Tiwari, M., and Thrun, S. MAPTree: Beat- ing "optimal" decision trees with Bayesian decision trees. Proceedings of the AAAI Conference on Artificial Intelli gence, 981999909 March 2024.
van der Linden, J. G., Vos, D., de Weerdt, M. M., Verwer, S., and Demirović, E. Optimal or greedy decision trees? revisiting their objectives, tuming, and performance. arXiv preprint arXiv::409. 12788, 2024.
Verwer, S. and Zhang, Y. Learning optimal classification trees using a binary linear program formulation. Pro- ceedings of the AAAI Conference on Artificial Intelli- gence, volume 33, pp. 1625-1632. 2019.
Xin, R., Zhong, C., Chen, Z., Takagi, T., Seltzer, M., and Rudin, C. Exploring the whole rashomon set of sparse de- cision trees. Advances Neural Information Processing Systems, 4071444444, 2022.
Zhou, Q. Liao, F., Mou, C., and Wang, P. Measuring inter- pretability for different types of machine learning models. In Trends and Applications Knowledge Discovery and Data Mining: PAKDD 2018 Workshops, BDASC, BDM, MLACyber, PAISI, DaMEMO, Melbourne, VIC, Australia, June 2018, Revised Selected Papers 22, pp. 295-308. Springer, 2018

---

Near-Optimal Decision Trees in SPLIT Second
A. Appendix
A.1. Further Comparisons With Other Methods
A.1.I. MORE DATASETS WITH DEPTH 5 TREES
In Section the paper, we showed results for three datasets. Here, we evaluate SPLIT, LicketySPLIT, and its contem- poraries on additional datasets. All datasets were evaluated on three random 80-20 train-test splits of the data, with the average and standard error reported. Results Figure 5. Note that Covertype has smaller error bars because the dataset size is much larger- it has 5 10 examples, while COMPAS and HELOC have only 10* examples.
12

---

Near-Optimal Decision Trees in SPLIT Second
Test Loss vs # Leaves for Different Decision Tree Algorithms
SPLIT (ours)
greedy topk (dl8.5)
tsdt gosdt
maptree
LicketySPLIT (ours)
murtree
covertype
compas
heloc
0.35
0.45
Test Loss
0.40
0.4
0.30
0.35
0.25
0.3
0.30
10
20
30
0
10
20
30
10
20
30
Number of Leaves
Number of Leaves
Number of Leaves
Test Loss vs Training Time for Models in the Red Box
Test Loss
0.26
0.36
0.31
0.34
0.25
0.30
0.32
0.24
0.29
10
10
10
10 Training Time (s)
10
10
10
10
10
Training Time (s)
Training Time (s)
Test Loss
Leaves for Different Decision Tree Algorithms
bank
hypothyroid
spambase
0.4
0.075
Test Loss
0.3
0.3
0.050
0.2
0.2
0.025
0.1
0.1
0.000
10
20
30
10
20
30
10
20
30
Number of Leaves
Number of Leaves
Number of Leaves
Test Loss vs Training Time for Models in the Red Box
0.13
0.03
Test Loss
0.14
0.12
0.02
0.12
0.11
0.01
0.10
0.10
0.00
10 -0
1
10
10
10
10
10 10 10
Training Time (s)
Training Time (s)
Training Time (s)
Figure 5. A performance comparison between our algorithm and those in literature. The lower row are zoomed in versions of the red boxes in the upper row. This complementary Figure and shows more datascts for completeness. The depth budget for all algorithms whose depth budget can be specified is 5.
13

---

Near-Optimal Decision Trees in SPLIT Second
A. 1.2. WHAT ABOUT DEPTH 4 TREES?
In this section, we perform the same evaluation above, but with depth 4 trees. We the lookahead depth as 2.
Test Loss vs # Leaves for Different Decision Tree Algorithms
SPLIT (ours)
greedy
tsdt gosdt
maptree murtree
LicketySPLIT (ours)
topk (d18.5)
netherlands
bike
adult
0.40
Test Loss
0.4
0.225
0.35
0.200
0.2
0.30
0.175
0
10
20
30
0
10
20
30
10
20
30
Number of Leaves
Number of Leaves
Number of Leaves
Test Loss vs Training Time for Models in the Red Box
0.190
Test Loss
0.32
0.20
0.185
0.180
0.30
0.15
0.175
10
10
10
10-1 Training Time (s)
10
10
10
10
103
Training Time (s)
Training Time (s)
Test Loss vs # Leaves for Different Decision Tree Algorithms
covertype
compas
heloc
0.35
0.45
Test Loss
0.40
0.4
0.30
0.35
0.25
0.3
0
10
20
30
0
10
20
30
10
20
30
Number of Leaves
Number of Leaves
Number of Leaves
Test Loss vs Training Time for Models in the Red Box
Test Loss
0.26
0.36
0.31
0.25
0.34
0.30
0.24
0.32
0.29
10-1
10
10
10-1
10
10a
10-1
10
10a
Training Time (s)
Training Time (s)
Training Time (s)
14

---

Near-Optimal Decision Trees in SPLIT Second
Test Loss vs # Leaves for Different Decision Tree Algorithms
bank
hypothyroid
spambase
0.4
0.6
0.075
Test Loss
0.3
0.4
0.050
0.2
0.025
0.2
0.1
0.000
10
20
30
10
20
30
0
10
20
30
Number of Leaves
Number of Leaves
Number of Leaves
Test Loss vs Training Time for Models in the Red Box
0.13
Test Loss
0.02
0.12
0.15
0.01
0.11
0.10
0.00
0.10
10
10
10
10
10
103
10
10
103
Training Time (s)
Training Time (s)
Training Time (s)
Figure 6. A performance comparison between our algorithm those literature. Depth Lookahead depth
15

---

Near-Optimal Decision Trees in SPLIT Second
A. 1.3. WHAT ABOUT DEPTH 6 TREES?
In this section, we perform the same evaluation above, but with depth 6 trees. We set the lookahead depth as Note that Murtree and GOSDT not included in the comparison they take much longer to run for deeper trees.
Test Loss vs # Leaves for Different Decision Tree Algorithms
SPLIT (ours)
topk (dl8.5)
greedy maptree
LicketySPLIT (ours)
tsdt
netherlands
bike
adult
0.40
Test Loss
0.4
0.225
0.35
0.200
0.2
0.30
0.175
0 10 30
0 10 20
0 2030
Number of Leaves
Number of Leaves
Number of Leaves
Test Loss vs Training Time for Models in the Red Box
0.32
0.19
Test Loss
0.20
0.31
0.18
0.30
0.15
0.29
10-1
10
103
10-1
10
103
10
10
103
Training Time (s)
Training Time (s)
Training Time (s)
Test Loss vs # Leaves for Different Decision Tree Algorithms
covertype
compas
heloc
0.35
0.45
Test Loss
0.40
0.4
0.30
0.35
0.25
0.3
0.30
0 10 2030
0
20000
0 2030
Number of Leaves
Number of Leaves
Number Leaves
Test Loss vs Training Time for Models in the Red Box
Test Loss
0.26
0.36
0.31
0.34
0.25
0.30
0.32
0.24
0.29
10
10
103
10
10
103
10
10
103
Training Time (s)
Training Time (s)
Training Time (s)
16

---

Near-Optimal Decision Trees in SPLIT Second
Test Loss vs # Leaves for Different Decision Tree Algorithms
bank
hypothyroid
spambase
0.4
0.6
0.075
Test Loss
0.3
0.4
0.050
0.2
0.025
0.2
0.1
0.000
0 1020 30
10
20
30
0 10 20 30
Number of Leaves
Number of Leaves
Number of Leaves
Test Loss vs Training Time for Models in the Red Box
0.13
0.03
Test Loss
0.14
0.12
0.02
0.12
0.11
0.01
0.10
0.10
0.00
10
10
103
10
10
103
10
10
103
Training Time (s)
Training Time (s)
Training Time (s)
Figure 7. A performance comparison between algorithm and those in literature. Depth Lookahead depth 2.
A.2. Many Near-Optimal Trees Exhibit Monotonically Decreasing Optimality Gaps Closer to Leaves
Consider an e-optimal tree T' E R(D, A, d). For a subtree t T, define Xe as the value of À that results in the greedy tree, Ty. having the same number of leaves as f. We now define the optimality gap 5(D,, t) as the difference between the loss of and the loss of an equally sparse greedy tree on sub-problem associated with This enables a fair performance comparison between greedy and optimal trees, as the training loss of any given tree will otherwise monotonically decrease with the number of leaves.
8(D,,t) t) = L,, A) - ( (t)th(t), At), Dr, At).
(5)
For a tree T E R, we then compute the average optimality gap associated with subtrees at each level. That is, given level é, we compute:
Σ ((DD,tt)lp rooted at level é]
BTT, BTT,D,))
KET
(6)
Σ 1lt rooted level !]
We want to determine if 3(T, D) is monotonically decreasing with & for given tree -' this is true, then being greedy closer to the leaf does not incur much loss in performance. Our intuition is as follows: if there are many such near optimal trees, then a semi-greedy search strategy could potentially uncover at least one them. The following statistic computes the proportion of all trees in the Rashomon set that have monotonically decreasing optimality gaps increases (i.e., moves from root towards leaves):
ml m(D. D, (D,A.c,d)= ETER(DANO 1[8 D, is monotonically decreasing with !
(R(D.A.e,d)
Figure 8 shows this statistic for Rashomon sets with varying values of the sparsity penalty X. We fix c = 0.025. The sparser a near-optimal tree, the more likely that it will be greedy, however, for all datasets, there exist near-optimal trees with monotonically decreasing optimality gaps even for low sparsity penalties. This has important algorithmic implications for developing interpretable models, because it means that search strategy that increasingly greedy near the leaves can produce near-optimal tree.
17

---

Near-Optimal Decision Trees in SPLIT Second
% - Decreasing Gap % Trees Decreasing Gap
adult
heloc
covertype
100
50
0
compas
bike
netherlands
100
50
0.005 0.010 0.015
0.020
0.005 0.010 0.015 Sparsity Penalty
0.020
Sparsity Penalty A
Sparsity Penalty A
Figure Percentage trees the Rashomon that exhibit monotonically decreasing optimality gaps. For sparse trees (i.c., where is larger), more likely find tree whose optimality gap is consistently decreasing cach level. This suggests that behaving greedily only near the leaves can produce a perfooeefo tree.
A.3. Miscellaneous Properties of SPLIT
1. WHICH LOOKAHEAD DEPTH SHOULD USE?
In this section, we explore the effect of the lookahead depth on the runtime and regularised test and train losses. We use the aggressively binarized versions of the datasets, elaborated in Section A.7.
compas
heloc
covertype
10a
10a
10
Training time (s)
100
100
10
10-1
10-1
10-1
10-2
10-2
10-2
netherlands
adult
bike
10a
10a
10a
Training time (s)
100
100
100
10
10
10-1
10-2/
10-2
10-2
2
3
1
2
4
0
1
3
4
Lookahead Depth
Lookahead Depth
Lookahead Depth
Figure 9. Runtime as function of the lookahead depth. = 0.001
18

---

Near-Optimal Decision Trees in SPLIT Second
compas
heloc
covertype
0.248
Regularised Loss
0.291
0.321
0.248
0.290
0.320
0.248
0.290
0.320
0.248
0.290
0.319
0.247
0.290
netherlands
adult
bike
0.181
0.148
Regularised Loss
0.300
0.180
0.146
0.180
0.290
0.180
0.144
0.280
0.180
2
3
4
Lookahead Depth
Lookahead Depth
Lookahead Depth
Figure Regularised training loss as function the lookahead depth. À = 0.001
compas
heloc
covertype
0.3175
Regularised Loss
0.24775
0.3150
0.24750
0.300
0.3125
0.24725
0.3100
0.295
0.24700
0.3075
netherlands
adult
bike
Regularised Loss
0.1874
0.31
0.148
0.1872
0.146
0.30
0.1870
0.1868
0.144
0.29
0.1866
0.142
1
2
2
0
2
3
Lookahead Depth
Lookahead Depth
Lookahead Depth
Figure Regularised test loss as function the lookahead depth. 0.001
From the figures, we see that there indeed exists an optimal lookahead depth that minimizes the runtime of SPLIT. At this depth, however, there only small increase in regularised training loss. Surprisingly, the test loss can also be lower at the runtime minimizing depth.
19

---

Near-Optimal Decision Trees in SPLIT Second
A.3.2. ARE SPLIT TREES THE RASHOMON SET?
This evaluation characterises the near optimal behaviour of trees produced by our algorithms. In particular, we're interested in understanding how often trees produced by our algorithms lie in the Rashomon set. To do this, sweep values of X. For each \, first generate SPLIT and LicketySPLIT trees and compute the minimum value of needed such that they are in the corresponding Rashomon set of decision trees with depth budget 5 - this is denoted by the respective frontiers of both algorithms.
adult
heloc
bike
0.008
0.00100
SPLT
SPLIT
SPLIT
LicketySPLIT
LicketySPLIT
LicketySPLIT
0.004
Epsilon (E)
0.006
0.00075
0.004
0.00050
0.002
0.00025
0.002
0.00000
0.000
0.000
compas
netherlands
covertype
0.008
SPIT LicketySPLIT
SPLIT LicketySPLIT
SPLIT LicketySPLIT
0.008
0.003
Epsilon (E)
0.006
0.006
0.002
0.004
0.004
0.001
0.002
0.002
0.000
10-3
10 -2
10
-.0000
10
10-2
1
10
0.000
10-3
10-2
10-1
Lambda (A)
Lambda (A)
Lambda (A)
Figure 12. An illustration near-optimality of our algorithms for depth budget 5. The light yellow region represents the (A, e) configura- tions for which only SPLIT produces trees in the Rashomon while the darker region represents (A, values for which both SPLIT and LicketySPLIT produce trees in the Rashomon set. The figure shows that our trees are almost always the Rashomon set even for small values of (c, A)
Figure 12 shows that this minimum small regardless of the value of While SPLIT has a smaller minimum c, implyyng a lower optimality gap. particularly noteworthy is the performance of LicketySPLIT. Despite admitting polynomial runtime, it manages to lie in the Rashomon set even for small 10-3
A.3.3. SPLIT WITH OPTIMALITY PRESERVING DISCRETIZATION
In this section, we briefly consider how SPLIT performs under full binarization of the dataset. For a given dataset, we perform full binarization by collecting every possible threshold (i.e. split point) present in every feature. We then compare the resulting regularised test loss and runtimes to that of threshold guessing.
For this experiment, we first randomly choose 2000 examples from the Netherlands, Covertype, HELOC, and Bike datasets. Larger dataset sizes would produce around 10t features for the fully binarized dataset, which would make optimization extremely expensive computationally.
We then produce versions of the dataset fully binarized version (which contains around 3000-5000 features for each dataset), and threshold- -uessed version (McTavish et al., 2022) with num_est imators 200. The latter ensures that the number of features in the resulting datasets is between 40-60.
For a given dataset, let D and Dig its the fully binarized and threshold guessed version. We then run SPLIT and
20

---

Near-Optimal Decision Trees in SPLIT Second
LicketySPLIT these datasets and compute the difference in regularised training loss between D and Dig- Figure 13 shows the resulting difference and the corresponding runtimes.
0.0025
SPLIT LicketySPLIT
Loss Difference
0.0020
0.0015
0.0010
0.0005
0.0000
heloc
netherlands
covertype
bike
102
Runtime (s)
101
100
10
heloc
netherlands
covertype
bike
SPLIT Full
LicketySPLIT Full LicketySPLIT Threshold Guessing
SPLIT Threshold Guessing
Figure 13. Difference in regularised training loss between SPLIT SPLIT/Lickee LicketySPLIT trained on fully binarized datasct the same dataset binarized using threshold guessing. We set 0.01.
We see that there is almost no difference in loss between the fully binarized dataset and the threshold guessed dataset, suggesting that there is minimial sacrifice in performance when using SPLIT LicketySPLIT with threshold guessing. Furthermore, using threshold guessing results in runtimes that are orders magnitude faster. These observations have also been corroborated by McTavish al. (2022), though in the context of vanilla GOSDT.
A.3.4. WHAT IS THE PERFORMANCE GAP BETWEEN GOSDT POST-PROCESSING FOR SPLIT LICKETY AND PURELY GREEDY P
We now examine the the additional improvement brought about by the GOSDT post-processing scheme for SPLIT and the recursive post-proee post-processing. We next illustrate the gap between SPLIT LicketySPLIT trees and tree that is trained purely using a lookahead strategy and behaving purely greedily subsequently. Concretely, we first solve Equation 8, i.::
+ min
if =
D
D
D
FEF ( (T(T( (17.00000..)))+(7000000....
C(D,d',A)=
A min
min
if d' = -d-d di
(8)
[D]
[D]
DD-1
|D+1
- -
A + min
min
d'd > d de.
[D]
[D]
JEF
Let Tc., the tree representing the solution to this equation this is lookahead prefix tree with greedy splits after depth de Let TSPLIT be the tree that replaces the greedy subtree after depth dj with optimal GOSDT splits this refers to lines 3-9 in Algorithm Let TISPLIT be the tree that replaces the greedy subtree after depth d, with recursive LicketySPL.I subtrees
21

---

Near-Optimal Decision Trees in SPLIT Second
(this refers lines 3-7 in Algorithm 3). We then vary the value of the sparsity penalty À [10-9, 1001] and compute the post-processing gaps the training dataset D:
L(Te.g: D,A) L[TSPLIT, D,
(9)
L(T2,g D, L(TESPLIT, D,
(10)
SPLIT
*
LicketySPLIT
compas
heloc
adult
0.15
0.06
0.3
Gap (%)
0.10
0.2
0.04
0.05
0.1-
0.02
0.00
0.0
0.00
bike
covertype
netherlands
1.0
0.4
0.75
Gap (%)
0.50
0.5
0.2
0.25
0.0
0.0
1
0.00
10 -3
10-2
10 -3
10
10
-3
10 -2
À
À
Figure 14. Gap (in % points) in accuracy between SPLIT LicketySPLIT and lookahead prefix tree followed by purely greedy approach. Depth budget = 5.
A.4. SPLIT and LicketySPLIT Scaling Experiments
We now evaluate the scalability of SPLIT and its variants the number of features increases. For each dataset evaluated, use the threshold guessing mechanism from (McTavish al., 2022) to binarize the dataset. In particular:
We first train a gradient boosted classifier with a specified number estimators Nest- Each estimator is a single decision tree stump with an associated threshold.
We then collect all the thresholds generated during the boosting process, order them by Gini variable importance, and remove the least important thresholds (i.e., any thresholds which result in any performance drop)
In this experiment, we choose in a logarithmically spaced interval between 20 and 10 to obtain binary datasets with 10-1000 features. We set a conservative value of À = 0.001 for SPLIT LicketySPLIT, as from Figure 12, this ensures that the optimality gap for our method is around ~ 10-3
Figure shows the results of this experiment.
22

---

Near-Optimal Decision Trees in SPLIT Second
SPLIT
LicketySPLIT
heloc
bike
Runtime (seconds)
10a
10
102
10a
10
100
10
10-1
10
10a
102
10
102
netherlands
+oovertppe
Runtime (seconds)
10a
10a
102
102
10
10a
100
109
10-1
10
102
10
Number of Features
Number of Features
Figure 15. Runtime of SPLIT and LicketySPI.T the number of features increases. À 0.001
23

---

Near-Optimal Decision Trees in SPLIT Second
A.5. Rashomon Importance Distribution Under RESPLIT TreeFARMS: Threshold Guessing
In this section, compare RESPLIT and TreeFARMS terms of their ability generate meaningful variable importances under the Rashomon Importance Distribution (Donnelly et al., 2023). This analysis is complete representation of that in Table 1. The variable importance metric considered is Model Reliance (MR) the precise details of how this is computed are in (Donnelly et al., 2023).
RID
RID With RESPLIT
bike Pearson T: 0.9994
heloc
compas Pearson 7: 1.0
Pearson T: 0.9784
Model Reliance
0.08
0.10
0.2
0.06
0.04
0.05
0.1
0.02
0.0
0.00
0.00
D
M
hiv
netherlands Pearson 0.9306
spambase Pearson т: 0.9304
Pearson T: 0.959
Model Reliance
0.100
0.06
0.075
0.050
0.02
0.00
0.000
Q
R
5
W
X
2
AA
AB
AC
AD
Features
bike
heloc
compas
10
10
10a
# Models
102
102
10a
10P
10"
10a
E
H1
M
hiv
netherlands
spambase
10
10
Models
102
#
10
T 10a
S
W
X
AA
A8
AC
AD
Features
A hr
..PrrontasccheeeeDeee Net hww.eeiiiiettnieigggnnnene
K: score facter
LINC00486
U: age at first penal cass
char freq
Bi inelant
Number,2e
P:PDD
V: of previous penil
AverageMinFlle
Age Above Fourtyfive
D: temp
I MaxdDelg2hublli Beci ast12M
N: Age. Bww.w. TwentyFive
MKLN1
X: 11-20 previnus case
AC: char.treq_]
MSince ideethhadeppen
African American
PTPRC
sex-temmaee
freq
Figure 16. (top) Model Reliance for the top features when the Rashomon Importance Distribution is computed in its original form (with TreeFARMS), and when RESPLIT is used as the Rashomon set generating algorithm. The reported Pearson correlation is computed between the top 20 features. We that is very close i.e. features that important under RID will also remain important when RESPLIT'S is used. (bottom) The number of models across the bootstrapped Rashomon sets which split on given feature. We note from the bar plots that RESPLIT also able generate large number of trees often times as many as TreeFARMS.
Parameters: À = 0.02, = 0.01, # bootstrapped datasets 10, depth budget = 5, lookahcad depth 3.
24

---

Near-Optimal Decision Trees in SPLIT Sccond
A.6. Rashomon Importance Distribution Under RESPLIT: Quantile Binarization
In this section, we show similar results as the previous section, but when datasets are binarized using feature quantiles. We chose 3 quantiles per feature (corresponding each 3rd of the distribution), resulting in datasets with 3x the number of features. For most of these datasets, RID with TreeFARMS failed to run in reasonable time.
bike
heloc
compas
Model Reliance
0.15
0.15
0.08
0.10
0.10
0.04
0.05
0.05
0.02
0.00
0.00
0.00
A
B
D
E
H
K
N
0
hiv
netherlands
spambase
Model Reliance
0.020
0.10
0.10
0.015
0.05
0.010
0.00
0.005
0.00
P
R
W
X
Z
AA
AB
AC
AD
Features
bike
heloc
compas
10a
10
104
10a
10a
10a
10
10a
101
10
10
10"
10a
10a
D
E
M
N
0
hiv
netherlands
spambase
10a
10a
10a
10a
10a
10a
10a
10a
10a
101
10a
10a
10a
10a
AA
AB
AC
AD
ParcontiradistevveDDel
LINC00486
age
B: stemp
G: Nettractonteevdiiigguuteen
L: Number of Priors
Q: PTPRC
V: log # previous penal cases
AAc char freq
C: temp
nFlle
M: Age Above Above_Fourtyyial Fourtyfive
SYTL2
W: sox=female
AB: word ford_freq_ho
MaxDeldEver
Age Below, Twentyfive
PPP3CA
X: country birth
AC: free_!
E: season
J: MSinceMMssRecentDekk
O: African American
ATXV1
Y. age in yearss
AD: capital run. length total
Figure 17. (top) Model Reliance under RESPLIT for the top features. (bottom) The number of models across the bootstrapped Rashomon sets which split on given feature. We note that the features which are important for RESPLIT under threshold guessing are also similarly important under quantile binarization, suggesting that our approach can generalize different binarization schemes.
Parameters: À = 0.02,e = 0.01, # bootstrapped datasets 10, depth budget = 5, lookahcad depth = 3.
25

---

Near-Optimal Decision Trees in SPLIT Second
A.7. Experimental Setup
A.7.1. DATASETS
In this paper, we performed experiments with 10 datasets:
The Home Equity Line of Credit (HELOC) (FICO, 2018) dataset used for the Explainable ML. Challenge. This dataset aims to predict the risk of loan default given the credit history of an individual. It consists of 23 features related to financial history, including FICO (credit) score, loan amount, number of delinquent accounts, credit inquiries, and other credit performance indicators. The dataset contains approximately 10,000 instances.
Two recidivism datasets (COMPAS and Netherlands). COMPAS aims to predict the likelihood of recidivism (reoffending) for individuals who have been arrested. The dataset consists of approximately 6000 instances and includes 11 features including demographic attributes, criminal history, risk of general recidivism, and chargesheet information. The Netherlands dataset is similar recidivism dataset containing demographic and prior offense features for individuals, used to predict reoffending risk.
The Covertype dataset, which aims to predict the forest cover (one of 7 types) for areas of the Roosevelt National Forest in northern Colorado, based on cartographic data. It contains 54 attributes derived from US Geological Survey data. These include continuous variables like elevation, aspect, slope, and others related to soil type and climate. The dataset has over 580,000 instances, each corresponding to a 30m x 30m patch of the forest.
The Adult dataset, which aims to predict whether an individual's 's income exceeds $50000 per year based on demographic and occupational information. contains around 50000 train and test examples, with 14 features.
The Bike dataset ( & Gama, 2013), which contains two-year historical log of bikeshare counts from 2011-2012 in Washington D.C., USA. It contains features relating to the weather at every hour with the aim being predict the number of bike rentals in the city in that given time period.
The Hypothyroid dataset, which contains medical records used to predict whether patient has hypothyroidism based thyroid function test results and other medical attributes. It includes categorical and continuous variables such as TSH Sthyroid-stimulatne hormone) levels, age, and presence of goiter, with thousands of instances.
The Spambase dataset, which consists of email data used to classify messages as spam or not spam. The dataset contains 57 features extracted from email text, such as word frequencies, capital letter usage, and special character counts, with around 4600 instances.
The Bank dataset, which is used to predict whether a customer will subscribe to a bank term deposit based on features like age, type, marital status, education level, and past marketing campaign success. consists of approximately 4500 instances with 16 attributes.
The HIV dataset contains RNA samples from 2 patients. The labels correspond whether the observed HIV viral load is high or not.
One reason for our choice of datasets was that we wanted to stress-test our methods in scenarios where the dataset has O103 - 100) examples - our smallest dataset has 2623 examples and the largest almost has almost 600000 examples. There are a number of datasets from prior work (e.g. Monkl, Monk2, Monk3, Iris, Moons, Breast Cancer) which only have O(10²) examples- for these, many optimal decision tree algorithms are fast enough (i.e. operating the sub-second regime) that limits any practical scalability improvements. Our aim was to go from the O(hours) regime to the sub-1 second regime, hence, chose datasets whose size would best reflect the performance improvements were hoping showcase.
A.7.2. PREPROCESSING
We first exclude all examples with missing values
We correct for class imbalances by appropriately resampling the majority class. This was the most prevalent in the HIV dataset, where we observed a 90 : 10 class imbalance. We corrected this by randomly undersampling the majority class.
26

---

Near-Optimal Decision Trees in SPLIT Second
All datasets have combination of categorical and continuous features, while SPLIT LicketySPLIT / RESPLIT and many other decision tree algorithms require binarization of features. We therefore the threshold guessing mechanism of binarization from McTavvsh et al. (2022), which can handle both these feature types. In particular:
We first train gradient boosted classifier with a specified number of estimators Pest- Each estimator single decision tree stump with associated threshold.
We then collect all the thresholds generated during the boosting process, order them by Gini variable importance, and remove the least important thresholds (i.e., any thresholds which result in any performance drop)
We store three binarized versions of each dataset for experiments with SPLIT and LickerySPLIT:
For version we chose fest for each dataset such that the resulting binarized dataset has between 40- 40-100 features. This is the version used for experiments in Figures 5, 6, 7 when we compare SPLIT LicketySPLIT with other datasets.
For version 2, chose Rest for each dataset such that the resulting dataset has around 20-25 features. This is the version used when we use the TreeFARMS algorithm (Xin et al., 2022) to generate Rashomon sets to explore the properties of near optimal decision trees, as TreeFARMS can be very slow otherwise. Figures 2 and 8 use this version of the datasets.
We additionally store another version of the datasets which is fully binarized, i.e., every possible split point is considered. Section A.3.3 uses this version the dataset is to justify the use of threshold guessing in the context of our algorithm.
Additionally, for aggressively binarized version of the dataset (i.c., version 2), we subsample Covertype so that it has 2J 20000 examples. This is again to ensure that the TreeFARMS algorithm runs a reasonable amount of time.
We also show scaling experiments for our algorithms, which are described in Section A.4.
Features After
Data Set
Samples
Features
Features After Binarization
Aggressive Binarization
HELOC
10459
24
62
23
COMPAS
6172
12
39
24
Adult
32561
15
65
23
Netherlands
20000
10
52
23
Covertype
581012
55
41
21
Bike
17379
17
99
23
Spambase
4600
57
78
23
Hypothyroid
2643
30
72
23
Bank
4521
16
67
23
Table 3. Characteristics of the datasets tested in this paper for LicketySPLIT and SPLIT experiments. We generate two binarized versions each dataset using the threshold guessing mechanism in (McTavish et al., 2022) which are used different sets experiments.
Data Set
Samples
Features
Features After Binarization
HELOC
10459
24
47
COMPAS
6172
12
39
Netherlands
20000
10
52
Bike
17379
17
99
Spambase
4600
57
78
HIV
4521
100
57
Table 4. Characteristics of the 6 datasets tested in this paper for RESPLIT experiments. As in Table 3, we use the threshold guessing mechanism for binarization.
27

---

Near-Optimal Decision Trees in SPLIT Second
A.7.3. DETAILS OF COMPARATIVE EXPERIMENTS FOR SPLIT AND LICKETYSPLIT
Greedy: This is the standard scikit-learn Decision class that implements CART. We vary the sparsity of
this algorithm by changing the min sain__smpllee es leaves argument. This is the minimum number of examples required to be in a leaf in order for CART to make further a split at that point.
GOSDT (Lin et al., 2020): We vary the sparsity parameter X, choosing equispaced values from 0.001 to 0.02.
SPLIT LicketySPLIT. We search over the same À values as GOSDT. For SPLIT, additionally, set the lookahead depth to be 1.
Thompson Sampled Decision Trees (TSDT) (Chaouki et al., 2024): Following the practices described in the Appendix Section B of their paper, we fix the following parameters:
- = 0.75
- Number of iterations = 10000
Additionally, we also fix the following parameters, based on the Jupyter notebooks in the Github repository of TSDT.
thresh,tree le
thresh.leaf = le - 6
thresh_mu = 0.8
thresh_si gma 0.1
To obtain different levels of sparsity, we vary the À parameter. We experiment with 3 values of A {0.0001, 0.001, 0.01J. For each value of X, we also experiment with different time limits for the algorithm: {1, 10, 100, 1000). Lastly, we use the FAST-TSDT version of their code, as according to the paper, it strikes a good balance between speed and performance (which is consistent with our paper's motivation).
Murtree (Demirović et al., 2022): For this method, we vary the max.num.nodes. which is the hard sparsity constraint imposed by Murtree on the number leaves.
For depth trees, choose ma x nwm.nodes in the set {4, 9,
10, 11}.
For depth 4 trees, we choose max_num.node the set {3, 4, 5, 73.
MAPTree (Sullivan et al., 2024): The paper has two hyperparameters, a and 8, which in theory control for sparsity in theory by adjusting the prior. However, the authors show that MAPTree does not exhibit significant sensitivity to a and 3 across any metric. Therefore, the only parameter we choose vary for this experiment num cammeexpasion We chose 10 values of this parameter in logarithmically spaced interval from [10", 103.5].
Top-k (DL8.5) (Blane et al., 2024): The paper also does not specify how vary the sparsity parameter hence, we vary k from 1-10.
Note that there is depth budget hyperparameter for MAPTree and TSDT, but we still show these algorithms across all experiments for comparative purposes.
Our method vs another bespoke-greete approach We briefly discuss another decision tree optimization algorithm from (Balcan & Sharma, 2024) that demonstrates good performance on a tabular dataset. This method first proposes novel greediness criterion called the (a:, -ss-lll entropy, defined as:
g(a, B) a-1 (1-1 p. p2)
(11)
where P {p.} } is discrete probability distribution. Then decision tree is trained in CART-like fashion, but with this greediness criteria instead. Note that
For the COMPAS dataset, which is one of the smaller datasets in our experiments, we conducted a brief evaluation by averaging results over 3 trials for 3 different values of the hyperparameters a and B, arranged in grid-based configuration as defined in (Balcan & Sharma, 2024). These hyperparameters influence the functional form of the above greedy heuristic. Below, we summarize the key settings and observations:
28

---

Near-Optime Decision Trees in SPLIT Sccond
Values of [0.5, 1, 1.5]
Values of [: [1, 2, 3]
Observations:
1. The method in (Balcan & Sharma, 2024) achieves approximately 31.6% test error with around 10 leaves, requiring an average of 10 minutes to train for single hyperparameter setting. Another thing to note is that it isn't It clear a-priori which hyperparameter will lead to the best performance (in terms of the desired objective in Equation 1), so many different combinations of hyyee--paaamteen might need to be tested order to find a perfopeero tree.
2. SPLIT achieves approximately 31.9% test error with fewer than 10 leaves in approximately 1 second.
3. LicketySPLIT achieves approximately 31.9% test error with fewer than 10 leaves in under 1 second.
In summary, our proposed methods are over 600x f'aster than (Balcan & Sharma, 2024), with a negligible difference in test performance.
A Note on Comparative Experiments with Blossom (Demirović et al., 2023) We briefly compare SPLIT with Blossom, an anytime decision tree algorithm incorporates greedy heuristics guide search order, albeit in a bottom up manner. To our understanding, Blossom has no hyperparameters we can tune (except depth budget, min size, and min depth), which limits its flexibility in adapting to various datasets.
Dataset
Runtime (s)
Test Loss
# Leaves
Blossom
LicketySPI.IT
Blassom
LicketySPI.IT
Blossom
LiP.
compas
0.442 [0.381, 0.476]
0.334 (0.332, 0,336]
0.314 [0.303, 0.323]
0.317 [0.305, 0.329]
32.0 [32.0, 32.0]
[8.0, 8.0]
adult
16.223 [15.556, 16.744]
1.459 [1.453, 1.465]
0.177 [0.175. 0.179]
0.177 [0.173, 0.181]
32.0 [32.0, 32.0]
7.3 [6.4, 8.3]
netherlands
6.161 128, 6. 194]
0.627 [0.622, 0.632]
0.287 [0.282, 0.291]
0.292 [0.288, 0.296]
32.0 [32.0, 32.0]
7.7 [6.7, 8.6]
heloc
27.179 [26.810, 27.548)
0,510 (0.502, 0.518]
[0.281. 0.291]
[0.286, 0.303]
32.0 [32.0, 32.0]
[6.2. 7.8]
spambase
18.334 [18.200, 18.478]
0.487 [0.482, 0.492]
0.090 [0.085, 0.094]
0.087 [0.085, 0.088]
32.0 [32.0. 32.0)
13.7 [13.2. 14.1]
bike
158.744 [157. 159 159.964)
1.679 [1.633, 1. 1.725]
0.112 108, 0.115]
0.121 [0.1 0.1255
32.0 [32.0, 32.0]
12.3 12.8)
hank
11.452 [11,053, 11.673]
0.353 (0.346, 0.360]
[0.097, 0.112]
[0.098, 0.1088
32,0 (32.0, 32.0]
(8.2, 9.8]
hypothyroid
2.799 [2.699, 2,909]
0,206 [0. 198, 0.214]
0.004 [0.002, 0.006]
0 [0.000, 0.002]
17.8 [15.4, 20.21
6.0 [6.0, 6.0]
covertype
13.617 [13.244, 13.861]
11.86 (11 1,75777 12.151]
0.237 (0.236, 0.238]
0.242 [0.241, 0.243]
32.0 (32.0, 32.0]
5.0 (5.0, 5.0]
Table 5. Comparison of Blossom and LicketySPLIT across datasets when Blossom is allowed to finish. We show the LicKetySPLIT configuration (after grid-search across A) that yielded the best test loss that dataset (averaged across 5 trials with depth budget 5). Only the mean is bolded when LicketySPLIT performs better. Values are reported as mean [lower, upper] (indicating 95% confidence intervals).
From Table 5, we see that, despite being allowed to run to completion (taking over 10x longer in many cases), Blossom often underperforms LicketySPL.IT in test loss. Furthermore, it much less sparse than LicketySPLIT, having over 4 as many leaves for similar test performances.
We ran another experiment to examine Blossom's 's anytime performance. In order to facilitate fair comparison, we made Blossom run for approximately the same amount of time as LicketySPLIT (i.c. generally ~ 1 second) on a given dataset. Table 6 shows the best performing tree found by LicketySPLIT (found by varying À and computing the resulting test loss) for each dataset compared with a tree found by Blossom (depth 5). We see that, given comparable runtimes, LicketySPLIT often achieves lower test loss with much fewer leaves compared to Blossom (which mostly branches out to 32 leaves).
29

---

Near-Opting Decision Trees in SPLIT Second
Dutaset
Runtime (s)
Text Loss
Leaves
Blossom
LickerySPI.I ITT
Blossom
PicketySPI.IT
Blossom
LicketySPI.IT
campus
0.436 [0.404, 0.454]
0.334 (0.332. 0.336]
0.314 (0.303, 0.323]
0.317 [0.305, 0.329]
32,000 [32.000, 32.000)
8,000 [8.000, 8.000]
heloc
0.996 (0.992, 1.000)
0.510 [0.502, 0.518]
0.285 [0.28 0.289]
0.294 [0.286, 0.303]
32.000 [32.000, 32 000
7,000 [6.184 7.816]
bike
1,896 [1882, 1.908]
1,679 [1.633, 1.725]
0.128 [0.125, 0.133]
0,121 [0.117,0.1 0.125]
30.000
[30.000, 30.000)
12.333 [11 [11.862, 12.805)
covertype
14.297 [138466, 14.604]
11.864 [11,577, 1211
0.237 (0.236, 0.238]
0.242 [0.241, (0221,0.2445) 0.245]
32.000 [32,000. 0000
5,000 [5.030, 5.000]
adult
1.722 [1.717, 1.727]
1.459 [1,453. 1,465]
0.176 [0.174, 0.
0.176 (0.173, 0.181]
32,000 [32,000, 32,000]
7.333 [6.390, 8.276]
netherlands
1.238 11.230, 1,246]
0.627 [0.622, 0.632]
0.284 [0.280, 0.287]
0.292 [0.288, 0.296]
32,000 [32. 010, 32,0000
7.667 16.724, 8.610]
bank
0.771 (0.765, 0.777)
0.353 (0.346. 0.360)
0.107 [0,099, 0.112]
0.103 (0.098, 0.108]
32,000 [32.000, 32.000)
9,000 [8. 9.816]
hypothyroid
0.649 10.635, 0.663]
0.206 [0.198, 0.214]
0.004 10,002, 0,006]
0.001 [0,000, 0.002)
18. 116.400, 21.200]
6,000 [6.000, 6.000]
spambase
0.832 [0.811, 0.856]
0.487 [0.482. 0.492]
0.091 [0.085, 0.097]
0.087 (0.085, 0.088]
32,000 [32.000, 32.000)
13,667 [13.196, 14.138)
Table 6. Comparison of Blossom and LicketySPLIT in anytime setting (i.e. Blossom execution is stopped around the same time LicketySPLITT) We show the LicketySPLIT configuration (after grid-scarch across À) that yielded the best test loss on that dataset (averaged across 5 trials with depth budget 5). Only the mean is bolded where LicketySPLIT outperforms Blossom. Values reported as mean [lower, upper] (indicating 95% confidence intervals). Note that the Blossom algorithm not able to explicitly account for sparsity, hence it always returns fully grown trees up given depth.
A.7.4. DESCRIPTION OF MACHINES USED
All experiments were performed on an institutional computing cluster. This was a single Intel(R) Xeon(R) Gold 6226 machine with 2. 70GHz CPU. It has 300GB RAM and 24 cores.
30

---

Near-Optimal Decision Trees in SPLIT Second
A.8. Appendix Proofs
Theorem A.1. Consider T, a tree output by LicketySPLIT, and T", tree output by method which is constrained to only make information ciariioongann-mmaxai gein-maainizing split at each node (or not split at all). Then, considering the training objective from Equation for training set D and given depth constraint d. we have: L(T, D, X) S ,
Proof. The proof will proceed by induction.
Base Case:
When there is insufficient remaining depth to split, or no split improves the objective, then T" and T both return a leaf with equivalent performance.
Inductive Step:
T considers the split that 7" would make (a greedy split), and evaluates the resulting performance of greedy tree after that split. It also considers all other splits, and evaluates the performance of greedy tree after that split. It either picks the split that 7" would make, or it picks one that will correspond to a tree better than T', assuming that the objective after the first split is at least as good as greedy tree past that first split (which, by the inductive hypothesis, we know is true).
Thus, by induction LicketySPLIT will do least as well as T'.
We can, of course, extend this SPLIT fairly trivially, since SPLIT is more rigorous than LicketySPLIT. The splits up the lookahead depth are optimal assuming the continuation past the lookahead depth is least good as greedy method (so SPLIT will either start with greedy splits up the lookahead, matching 7", or it will find some better prefix with respect to the training objective). The post- post-processing further improves the performance of SPLIT relative to T".
A.8.1. 1. PROOF OF THEOREM 6.1
Theorem 6.1 (Runtime Complexity of SPLIT), For dataset D with ie features and samples, depth constraint d such that < k, and lookahead depth 0 S di < d, Algorithm 2 has runtime On(d - di) + nkd-d)). If we cache repeated subproblems, the runtime reduces to Of n(d n(d-d:)""- nk (d-d:)1
d,1
Proof. We divide the computation process into two stages:
Stage 1 involves computing the lookahead tree prefix. There are k choices split at each level, yielding 2k nodes at the next level and hence (2k)4 nodes (sub-problems) at level d,. For each of the (2k)4 sub-problems at depth d,, we will compute a greedy subtree of depth d - d. Let S; be the ith sub-problem at depth di (with corresponding size {S;)) The runtime of a greedy decision tree algorithm with depth dg for a sub- sub-problem of size n and & features is Onkdg)) (where dg = d di in our algorithm). The runtime complexity for this phase is therefore:
(2h)
-0(10)
(2k)
(I-dd)(a- (i)dd))(d di)
Σ
S.|(k:
di)) =o
Σ S
(12)
where have (k - dd) features remaining be split on at the end of lookahead. Now,
(2
Σ
|S| 0 (nkktt)
(13)
because at each level, we split on O(k) features and route n examples down each path. Thus, the runtime for this stage simplifies to:
(2k)4
| dd) - di) = Onk d:) - d:))
(14)
A=1
On((d- di)
(15)
31

---

As the total sum of sub-problem sizes across all leaves is equal to Near-Optimal Decision Trees in SPLIT Second
where the second equality stems from the fact that k redundancy here, because this expression assumes that all sub-problems level de unique this is not the case. Consider subproblem identified by the sequence of splits fi = 0 f2 = + fa 0. The exact order of the splits does not matter in identifying the subproblem. This implies that multiple sequences of splits correspond to the same subproblem, leading to an overestimation of the runtime. At level d, there are therefore d,! redundant subproblems (corresponding to the different ways of arranging the sequence of splits). We only need to solve, i.c. compute greedy tree, for one of them and store the solution for the other identical subproblems. we cache subproblems this manner, the final runtime for this stage becomes:
O(k), because < and dj < d. However, there is
o (n(d (nidd- dd)dh+t) di!
(16)
Stage 2 involves replacing the leaves of the learned prefix tree with optimal tree of depth d di so that the resulting tree has depth S d. Let u be a leaf node in this prefix tree and nu be its corresponding sub-problem size. As before, we will search over all trees of size d d, which requires evaluation of (2k))d-d nodes in the search tree. This time, however, the evaluation at the last node will be linear in the sub-problem size (as we are not considering any splits beyond depth d). By the same argument as Stage 1, the runtime of this phase is therefore (k: nu). Summing this across all subproblems u, we get E,,
the original dataset size, this sum is equal to O (k) By the same subproblem redundancy argument as in Stage 1, the final runtime complexity of this stage upon caching redundant subproblems becomes:
nk de 0
(17)
di)!
Combining Stages and 2, we get that the total runtime SPLIT is:
(n(d - di) nkdddd)
Without Caching
(18)
n(d-di)adltt del
nk d-
With Caching.
A.8.2. PROOF OF COROLLARY 6.2
Corollary 6.2 (Optimal Lookahead Depth for Minimal Runtime). The optimal lookahead depth that minimizes the asymptotic runtime of Algorithm 2 is dN (d-1) for large k regardless of whether subproblems are cached.
Proof. We evaluate the optimal lookahead depth in both scenarios, caching and no-caching.
Case 1: Lookahead Without Caching
In this case, the runtime expression is O (n(a di) d1)x.++1 + nhd-d)). We divide the proof into parts:
Part 1: Finding the stationary point of the runtime
32

---

Near-Optimal Decision Trees in SPLIT Second
Consider the runtime expression from Theorem 6.1. We now minimize this with respect dy:
0
n(d - (1) nh:ddd))
(19)
dd
(d - d1)h 11+ + kd-di) =0
(20)
0d;
ddddtt1 dik + kd-d)) =0
(21)
Od
d(log 16) +1 - (1+++1 1 + dlol k)) (log k) = 0
(22)
((d di) log 1) kat+1 (log ki) hhaaddi =
(23)
1 k2d+11 = kdd.
(d - d1) log ks
(24)
We can now simplify this equation to analytically express the lookahead depth di as a function of k. To do so, we define a new variable u such that:
V - 2 + 2d log k d:
(25)
log
Under this definition of d,, we can now rewrite Equation 24 in terms of u:
2- 2d lo
log e log 1(2((
21
2logh
)+1)
k2a
(26)
2log k
u + 2dlog
2 2log )em -= 20-2222 log k-Hlog kda
(27)
-u
2g 6" ====k kdd
(28)
2log k
uc 222e2k kx222=((41)) log k.
(d++1)
(29)
As the solution to this equation known be analytically intractable, we express u in terms of the Lambert W function, which is well known function that cannot be expressed in terms of elementary functions. Denoted by W (2), the Lambert W function satisfies the following equation:
(())
(30)
From Equation 29, we can express u in terms of W.), giving us:
k- (d++1 logk).
(31)
Substituting this back into the expression for d, Equation 25, we get:
di W(- -dd+1) log k) 2 + 2d log k:
(32)
log
Part 2: Bounding the Lambert W function
Let & = -2222k-dtt lo For sufficiently large k, 2 E 2. In this domain, there are two possible values of (()), Wo(z) and W=1(>), such that Wo(z) 2 W=1(z). Figure 18 shows these two branches of the W function.
33

---

Near-Optimal Decision Trees in SPLIT Second
Wo
W.1
Figure 18. The Lambert W function, which has branches in the real plane, Wo(z) and W-1(2). Figure from (Lóczi, 2021).
For now, consider the function W-1(s). We will show later that choosing this branch of the W function results in the value of di that minimizes the runtime. (Chatzigeorgiou, 2013) show the following lower bound for W-1(2):
(-1 log (-2) 22(11 - 1log (-2)).
(33)
(Lóczi, 2021) show the following upper bound for 1=1
W-1(2) < log (-2) log (- log (-2)).
(34)
Denote the lower bound as Thh (z) and the upper bound as (2). We can now write upper and lower bounds for the optimal di (call this d?) in Equation 32.
bh (2) 2 + 2d k
di W (2) - 2 + 2d log k
(35)
2 2log k
2log k
where k2e2k-(d++ log k from above.
Part 3: Lower Bound for di
We now evaluate the lower bound for di, substituting 35:
k (dd1) log into the left side Equation
di 2 1ith (2) - 2 2d log kt
(36)
2 2logh k
libh k- (d++)))
log k) 2 + 2d log
(37)
2 log k
log (2c2k-(d+1) log k) 2 2 (-1 log (d+1) k:) 2 + 2d log k
(38)
2 2log t log 2 -(d+ 1) log log log & 2d log k
V 2log 2(d 1) log k log log k
(39)
2 log k
34

---

Near-Optimal Decision Trees in SPLIT Second
Consider the term:
V-6 2og + 2)d -
lloglog
(40)
As & becomes large, we can ignore the constants. Asymptotically, log k log log ks and hence this term approaches
/ 22 + log k. Thus, we write:
log 2 (d + log k + log log k. + 2d 2d k. / 1) log K
di 2
(41)
2 log k
d+ +
log 2
log log k log k
2( 1)
d
+
+
(42)
2
2 log k
logk
d
0
(43)
Vlog k
as d a constant and >
Part Upper Bound for dj
We can similarly evaluate the upper bound for dy:
dj x --2e= (d+1) log k) - 2 + 2d 2dlog k
(44)
2log
log k2e2k- (d+ (d++1) log k) - log (- log k- log+)
-log
2 + 2d ic
(45)
2 logg k
log 2 (d 1) log + log log log
- (log + (d 1) log + log k)g
+ 2d log k
(46)
2log
Consider the term:
log - (log 2 + 2 2 (d log k log log k)).
(47)
As k becomes large, we can ignore the constants. We can also consider the asymptotic lower bound of the subsequent expression:
1
log (d+ log log log
(48)
(d + 1) log log log
we plug this lower bound Equation 46, the resulting expression is still valid upper bound.
log 2 - (d + 1) log l: log log k- 1 +
log + 2d k:
di <
(49)
2 logg k
d
++1
log 2
log log A:
dl
+
(50)
2
2 log
2 21og l
2(d + 1) log' h 2 log k log log k
d-1
1
0
log log
(51)
2
log k
Part 5: Putting it together
Finally, we get the following lower and upper bounds the optimal lookahead depth di:
d 1 o S s < d-1 1 + o log log
log k )
(52)
2
Vlog
k
2
For large k these bounds will converge, and hence, this limit, dj d-1
35

---

Near-Optimal Decision Trees in SPLIT Second
Part 6: Verifying that di d=1 is the minimum
We show that the computed value of dj is indeed the minimum by evaluating the second derivative of the run- time, i.e. @ nn(d- di) + nk ldi=d;- 8df
0² nn(d - di) + +nkadd)==
① (n((d- - di) log k 1)hu+1 nllog ())aad))
(53)
duf.
Odh
where we use the the derivative expression from Part 1 of this proof. Simplifying further:
0
(n(ld -i) log k: 1) n(log k) k:)aa-a)
(54)
0d
(ndk logk nd + log l nk nkk-aa log
(55)
Odi
rdll log k mh log de log² re log + nkdd log² k.
(56)
We now substitute di d-1 and simplify the result:
0² ddp
n(d di)kat+1 + +nk
(57)
di=d;
ndk 1+1
log² k - nk + log k
d (d-1 # log² k - nk 4
log k: + nk 4 log² k
(58)
+ 1
k: 4 log 2 1e + nk 1-1 log h 2nk " log k
(59)
2
n
+
3
k:
d+1
log² k - 2nk log k.
(60)
2
This is clearly > 0 as the log² terms dominate log k. Thus, the value dj = d-1 runtime.
corresponds to the minimum of the
Case 2: Lookahead with Caching
In this case, the runtime expression is O (n(d-d)A-1 dil
nk nt= (d- d:)l
We divide the proof into 3 parts:
Part 1: Finding the stationary point of the runtime
We can replace the factorial in the runtime expression with the Gamma function, i.e.:
4l = r(d + 1)= ( p dt
(61)
36

---

Near-Optimal Decision Trees in SPLIT Sccond
as this allows us to apply the derivative operator. Further employing the definition of the Digamma function vxx) = T(z) we now minimize the runtime with respect to d;
[()x)
a n(d d() r(d: 1]
nka de
I(d di + +1) +1) =0
(62)
dd
0
(d di)h:dit1
ho-d.
+ dd
T(d, + 1)
+ n dd,
[[dd - di + 11
=0
(63)
+
0
(id - d())
1
(d
di)h+++
rdd + 1)
+
(64)
0d;
I(d 11)
I(d: + 1)2
dd
0 (
ba-d
a r'dd dl + 1)
n
dd
I(d - di +1+1
[(d - di + 1)²
dd
=0
(65)
T(di+1 11 (d- digh
+
Rdetl + (d - di)k"i-1 log
T(dh + 1)2 [(d + 1)) + +1) +
(66)
1
kd-di
n
Rd log
I(d di +1 "[(d - dl + 1)²
[(dd- di + 1) - di 1) 0
(67)
hdi+1 (d - di) +1 log [c) + +1) (d di hhh T + () +
(68)
I(d + 1)2
de (T(d di + 1)b(d - di + 1) (log T) - di + 1)) =0
(69)
l'dd - di + 1)2
Simplifying this expression, we get:
( h-idi+1 + (d d.)h: +1 log k) - (d - de) (b) +1) hd-di ( + 1) log k)
= 0
(70)
I(d: + 1)
I(d - di + 1)
bd++1 -1 -11 (d - di) (log ks - v/ (d + +1))) ka-do de loogk - --dd- - dl + 1)
(71)
[(d: 1)
I(d di + +1)
2d dd+1
- 1 + (d di) (log k: - 1b (de + 111)
log k v(d di + 1)
(72)
I'(c + 1)
I'dd - di + 1)
log k </dd - di + T)) +1)
- 1:2d dd+
(73)
[(d di + 1)
- 1 (d - di) (log k & (ds + +1)
Part 2: Bounding the Optimal Lookahead Depth
Unlike the previous case, it is not possible to derive closed functional form for the optimal lookahead depth for any given value of h (although we can simulate it numerically). Instead, we need to analyze how this expression behaves as in the limit as i + oc. Because k >> d, dr. log k > vidd di + 1). Similarly, log k >> (idc, + 1). Furthermore, we can ignore all expressions which are not functions of l: as they are insignificant when is large. Thus, in this limit:
['d: + 1) log k:
(74)
I(d - dl + 1) - di) log k
[(4 + 1)
+ 2dddd+1 d+1
(75)
l'd - d: + () di)
+ (2d)- - -d+ + 1) log k = log I'd: + 1) - log - di + 1) - log(d - di)
(76)
+ 2dg- - d + 1 log (d, + 1) - log r'd di + 1) - log(d di)
(77)
log k:
37

---

Near-Optimal Decision Trees in SPLIT Second
Observe the term log [(d 1) log [(d d4 1) log(d di). We write the factorial form of this expression understand it better:
di! Io + 1) log [ di + +) log di) log (d di)!(d - di)
(78)
Notice that for any di between 0 and (inclusive), the RHS is always less than 0. Similarly, for [ < di S 1, the term is always greater than O. Given that these are constant as At increases:
log [(d: + 1) - IogI'd di + 1) log(d - -d) = -0(1 0
(79)
011) [ <
This implies:
log [(d + 1) loo [(d di + 11 - log(d - di) s 0
log k v
(80)
log k
log
for all 0 S di S d (which are the constraints in our setup). Hence, we conclude that, for large k:
< 2d
d+1s -0
(81)
logk
log k
d-1
O
S d s
+
(82)
2
log k
2
log
which approaches d, = d-1 as k >> c0. Henceforth, we denote this asymptotically optimal value as d/.
Part 3: Verifying that di d-1 the minimum for large
We show that the computed value of di is indeed the minimum for large le by evaluating the second derivative of the runtime, i.c. a (ndddd)4--1 ad del
+ nb 2g
Id==d;"
níd di) di nkddd:
+ (d di)!
(83)
ddp
di!
(-kdit1 + (d di hdtt+ log k)1 + 1) - (d -(d-d)kd++1pp + 1)b(d +1)
(84)
Od,
T(d 1)2
d
(Td dj + 1))b(d (d- - dl 1) (log k) d; + 11]
(85)
[(d - dl + 1)2
38

---

Near-Optimal Decision Trees in SPLIT Second
We can remove the dataset size n for simplicity it doesn't it affect the sign of the answer. In the limit l - oc, we can simplify this expression and only evaluate terms that grow with k:
0
log k(d dj)4 + HTdd 11 ka-d log (d di +1)
(86)
0dk
T(di + 1)2
I(d di + 1)2
log k(d-k(d)))) - (d(ddd)))(t+)) de))
r(ch +1)
log k(d - di)k [(d + 1)
[(d + +1)
(87)
Odl
[(d + 1)3
odi
(au-de log (k
[(d - di 1)
ha-di log k
T(d dj + 1)
(88)
Odl
[(d di + 1)
I(d di + 1)2
dd;
1
log k(d di) di)k I[(d + 1) + +1)
log kh + (d di)k (log (1og
(89)
[(d: +
r(d: 1)²
Rd-di log hi
bd (log k))) ríd dl +1)
-T(d di + 1) - di + 1)
(90)
r(d - dj + 1)3
log kk +1 + (d - d1) "log k))
log k(d di) + +1
(91)
T(d: + 1)
d: (log 1:)2
kdl-di log kub(d - di + 1)
(92)
[(d= dd - di + +1
r(d di + 1)
Ad+t! (logk) (d di) 1+ +1 (log k)2 - log k(d + + 1))
(93)
T(d: + 1)
dd-di (log k:)2 kd-di di log kid di + 1)
(94)
r(d di 1)
Note that the (log 2 terms are dominant in this expression as k - oc. Hence, at d7 d-1 sign of the expression are:
2 tte terms that will affect the
d (d+1) (log k))² k d (log k)² O(log k))
k 2
(95)
This is clearly positive for any d >>> 1, hence the value di d-1 corresponds to the minimum of the runtime. Note that in practice, if df is not an integer, we can choose whichever of [dū] or [di] gives us a lower runtime.
From Figure 19, we see that for a depth budget of 5, the minimum lookahead depth di is slightly less than 2 for both the caching and non-caching case, which is what is predicted by Corollary 6.2. This also lines up nicely with what we observe in practice (e.g. in Figure 9). Note that our algorithms, which build on the GOSDT codebase, cache subproblems by default.
A.8.3. PROOF OF COROLLARY 6.3
Corollary 6.3 (Runtime Savings of SPLIT Relative to Globally Optimal Approaches). Asymptotically, under the same conditions as Theorem 6.1 and with caching repeated subproblems, Algorithm saves a factor of O k d-1 relative to globalty optimal approaches (e.g., GOSDT).
(9)) in runtime
Proof. Any branch and bound algorithm for constructing a fully optimal tree will, in the worst case, involve searching through (2k)d sub-problems at depth (where we can ignore all sub-problems at shallower depths, because their cost is exponentially lower). By the same arguments as in Theorem 6. the runtime of brute force search without any caching
Onkk"). Thus, the ratio of runtimes of brute force and Algorithm 2 is O
kdt
From Theorem 6.1, set
(d- (8-d,)6411
41
(d 43
39

---

Near-Optimal Decision Trees in SPLIT Second
Depth Budget: 5
Depth Budget: et:
Optimal Lookahead Deoth
With Caching
2.25
Without Caching
10a4.
2.00
Runtime
10
1.75
1.50
10
1.25
With Caching
10a.
1.00
Without Caching
(d- 1)/2
0.75
0
3
4
1012 1015
10
Lookahead Depth
Number of Features
Figure 19. (left) The asymptotic runtime expression as a function of the lookahead depth for k = 20, d = 5, and n = 1000. This also lines up nicely with what we observe practice, e.g. in Figure (right) Exact value the theoretically optimal lookahead depth as function of the number of features (with their associated lower and upper bounds). T
d: d-1 as it minimizes the denominator of the above expression and hence gives the maximal runtime savings. Thus, the ratio runtimes is:
kd
(96)
- di +4
bd-dd
+
dc-
hd (+ي1 )!
0
(97)
1+1 k +
k- ((+1)
(98)
4+3 k -
oK x (
(1)
(99)
A.8.4. PROOF OF THEOREM 6.4
Theorem 6.4 (Runtime Complexity of LicketySPLIT). For dataset D with & features and n samples, and for depth constraint d, Algorithm 3 has runtime O(nk2d d
Proof. Sketch: Running lookahead for a single step involves & different potential splits, and a full run of a standard greedy algorithm for each sub-problem. Since a greedy algorithm's 's runtime for sub-problem of size n, is On,kd)), and each split creates two sub-problems whose sub-problem sizes sum to n,, we know that each split leads to O(nkd) runtime, and we have & such splits evaluate, leading to (nk-2d) runtime for the first iteration.
In the recursive step, call lookahead analysis.
sub-problems whose sizes sum n, and each of which has similar runtime
We run most d layers of recursion. From this, we have total runtime bound of Onnk?d), since we have levels which each take O time. Proof via recurrence relation:
For dataset and remaining depth d, and defining i' as the split selected by LicketySPLIT the current iteration, we have the runtime recurrence relation:
T(D,d)= T(D(it), -)) 1)) (0(1))))))(())++)))))))))))>)))) (0(1)))+((P()))))))) ((((())))))(())))) d 1 D
(O(DD))
d= 1
40

---

Near-Optimal Decision Trees in SPLIT Second
because each level and each feature, LicKetySPLIT needs to compute the split (O(ID)) time), then run greedy on the left and right subproblems, taking ((((())kk)) and O(ID())kk) time, respectively. Then needs recurse the optimal of those splits.
Noting that [ = ID], this simplifies to:
o(DDkk))
d>1
T(D,d)= (0(1D))
d=1.
Given this recurrence,
show d) O(n22d2) inductively.
First, define Ca, RA be values such that the runtime of each O(IDI) steps in the recurrence above is below сд [D] for k > kA, [D] > nA (we know such values exist because of the definition of O). Then define B. d kn be values such that the runtime of each ((d)) step in the recurrence above is below * DD] for k > kB, |D| > nB, d > 1 (we know such values exist because of the definition O). Now set:
ca, 1)
no = (AA, ko = max(k
do =
so that, for any k 2 ko. |D 2 no. d 2 do we can bound all the O(DD) steps as taking less than c| time, and all the ((dd) steps as taking less than c|D kdd time.
T(D,d) ((D
E (dD1) + c/Dlkd)
d>l
(DD)
d=1.
We now want to show that for any k 2 ko, D n 2 no, 2 do we can bound the runtime of the recurrence T as I cn, where n = DD.
We show this by induction:
Base Case (d- 1):
Trivially, 1) s c|Di of for any t 2 ko, DD 2 no. Note that k2d 2 because each of and d are at
least 1.
Inductive Step (d 2 2):
Now, inductively:
& TDD05ST0C))--1))000))))-1111 Σ [(DI+cDDkk))
(100)
T(D,d) 11000-~0000X0---70000---------00
(101)
Sck (0000-=9||(00--00000000000001100
(102)
S sck ("0(=="((0))<ppk==0>)
(103)
< cdD)
(104)
(d 2
(105)
s df noting that d 2.
(106)
Thus as [D] = n, we have the runtime dd..

---

Near-Optimal Decision Trees in SPLIT Second
A.8.5. ADDITIONAL CLAIMS, WITH PROOFS
We here prove some additional results about how our trees compare optimal ones.
Theorem A.2 (Optimality certificate based on lookahead depth), Algoritim 2 will return a tree with objective no worse than globally optimal free with maximun depth dlookahead-
Proof. Note that Algorithm 2 considers all possible tree structures up to depth diockahead- with greedy completions of those structures. Those greedy completions
worse than leaves with respect to our objective- they only expand beyond leaf if the regularized objective is better than leaving the tree node as leaf. So for any tree t of depth at below diookabead- there exists an analogous tree in the search space of Algorithm 2, with objective no worse than that of t.
Now, note that Algorithm 2 globally optimizes over its search space. So the tree returned by Algorithm 2 has objective no worse than any other element in the algorithm's ' search space.
We now have that the returned by Algorithm has objective no worse than a globally optimal tree with maximum depth dhookahead- For any globally optimal tree t" of that depth, we know there exists analogous tree 1' in the search space of Algorithn 2, with objective worse than that of t". And we know that the tree returned by the algorithm is no worse than tree l', and thereby no worse than L*.
(Note that postprocessing does not change the above, since it only ever improves the objective the reported solution). U
Theorem A.3 (Conditions for heuristic optimality). If any true globally optimal tree uses greedy splits after depth d,, then SPLIT will return globally optimal tree.
Proof. We prove Theorem A.3 as follows:
Our algorithm globally optimizes over the set of trees that use greedy splits after depth d,. Thus, if at least one such tree in that set also in the of globally optimal trees, know we will find that tree or another equivalently good tree according to our objective. (Note that postprocessing does not change the above, since it only ever improves the objective of the reported solution).
A.8.6. PROOF OF THEOREM 6.5
Theorem 6.5 (SPLIT Can be Arbitrarily Better than Greedy). For every e >> O and depth budget d, there exists a data distribution D and sample size n for which, with high probability over random sample S D Algorithm 2 with d: d-1 achieves accuracy at least 1 but pure greedy approach achieves accuracy at most +
Proof. Our proof follows similar construction as (Blanc et al., 2024). They define the function Tribes as follows:
Definition A.4 (Tribes: from Blanc et al. 2024). For any input length k. let w be the largest integer such that (1 - (1-2-w)er) 2. For x {0, 1 let (1) be the first w coordinates, (2) the second w, and so on. Tribes, defined as:
Tribes;(x) (xx)) A.... A Ax(2) V... v (x{" A A.... A xx
(107)
where t
Blanc et al. (2019) prove the following properties of Tribes:
Tribes, is monotone.
Tribes is nearly balanced:
E Ex- (o.1) (Tibes;(x)) (xxrro.yyTTibbs((ss)
2 + o(1)
where the (1) term goes to O as & goes to co.
All variables in Tribes; have small correlation: For each E [t].
Cov Covx<<(0.1p Txib = O log
42

---

Near-Optimal Decision Trees in SPLIT Second
Further define the majority function follows:
Definition A.5 (Majority). The majority function indicated by Maj 10, {0, 1). returns
Maj(#) {at least half of x's coordinates are 1].
Let the number of features k d1 + for lookahead depth de and constant u. Define the following data distribution over {0, 13 {0,1}:
Sample x ~ Uniform ((0.1)*)
Let x()) be the first dj elements in x and (dd) ) be the remaining elements. Compute:
Tribesa (x(di)) with probability 1 1-6 E, Majority
y = f(x)
(108)
with probability
How does lookahead fare on this data distribution?
Consider our lookahead heuristic. If we exhaustively search over all possible features up to depth di, we are guaranteed to perfectly classify Tribesa, (x(d))), , it is computed from dj features. In this scenario, the lookahead prefix tree will be full binary tree, with 24 leaves corresponding to every outcome of Tribes. When we extend this tree up to depth d (with or without postprocessing), Algorithm 2 is still guaranteed to achieve at least 1 accuracy.
How does greedy fare on this data distribution?
We now apply Lemma 4.4 from (Blane et al., 2024) in this context, adjusting the notation to suit our case. Let T be the tree of depth returned by greedy. Consider any root-to-leaf path of T that does not query any of the first di features of x (i.e. the Tribes block). Only features from the Majority block are therefore queried by T along this path. We can therefore write the probability of error along this path:
[xx) =yl follows this path] (x,y)>
Pr
= =(1 (1- Pr (T(x) Tribesa, (x(d:) x follows this path] (x.1)D
t Pr [x() Majority(x(di) x follows this path]
(x.1)/~D
$ (1 c1- +()) +
< 1 + é
2 + o(1
where the last line follows, because Tribes is nearly balanced. As the distribution over x is uniform, each leaf is equally likely. (Blanc et al., 2024) then show that, if only p-fraction of root-to-leaf paths of I' query at least one of the first di coordinates, then:
Pr T(x) = y (1 - p) (x.W)D
1+e
+ +o(1)) + p.1
(109)
2
+ _ +11)
+ 2
(110)
We now want to show that, just like in the case of (Blanc et al., 2024), p is small asymptotically, If this the case, we can claim that a greedy tree is arbitrarily bad. The only difference between (Blanc al., 2024) and us is that their greedy tree has depth dj (adjusting for notation), but want construct tree of depth d.
We now use Lemma 7.4 from (Blanc et al., 2019), which proves the following (again, adjusting for our notation): A random root-to-leaf path of a greedy tree T satisfies the following with probability at least - Ou If the length of this path is less than O w ) at any point along that path, all coordinates within the majority block that have not already been queried have correlation at least To Now, for a greedy tree of depth d:
43

---

Near-Optimal Decision Trees in SPLIT Second
We need to set u 2 (d log d) so that all root-to-leaf paths have length at most O so the above lemma applies.
log
Remember that the size our Tribes block is still fixed as the lookahead depth di, according to Equation 108. From the definition of tribes, all variables in this block will have correlation O log di
Because we want the correlations the
majority block to be greater than those in Tribes, we need to set 100.7 2 f2 dt
implying that u S O
df log
Thus, it follows that = O(u if the conditions above are satisfied. we set dj = 1-1 = O(), we can say that, for any Og d) I u S O log? greedy tree depth will yield accuracy & 1 from the Tribes block.
2 + c, as it almost never selects any variable
Theorem A.6 (All Trees in RESPLIT Can be Arbitrarily Better Than Greedy). For every e, > O, depth budget d, and lookahead depth di Rashomon set size R, there exists a data distribution 'D and sample size n. for which, with high probubility over a random sample ~ Dn, all trees oulput by Algorithm 5 with minimum runtime lookahead depth d: = d-1 achieve accuracy at least c- + (cc') but a pure greedy approach achieves accuracy at most 2 + c.
Proof. We divide the proof as follows:
Part I: Defining the feature space
Let the number of features k R + 2d for depth budget and constant that the size of the Rashomon we want generate. We now create a dataset of size with features the following manner:
Loop over iterations:
Sample ..... .2a uniformly from {0, 1]ad
For each 2d < j S 2d + R:
Choose a random index idæ(j) ~ Uniform d
Define feature Xj in the following manner:
Xide(i Xide())
With probability 1
Xj
(111)
otherwise.
Define the reference block of features to be XI....,XX. Xa. We break this block into 2 sub-blocks.
Sub-block corresponds the dj features for which we will compute parity bit. At high level, tree needs know the parity of the expression in order to 'unlock' high accuracy. This also serves to 'trick' greedy into not choosing these features, because they will have 0 correlation with the label. Let Xi Xa, be the features in this sub-block.
Sub-block 2 corresponds to the set of d - di features over which we will take majority vote. We will only reach this block when the parity bit is 1. Let X
Xa be the features in this sub-block.
Part 2: Defining the labels
For each example in this dataset, define the label y as:
(Xi o ..... Xa,) ) (xaority(Xa+11.... Majority(XA.. X2d)
with probability 1-6 with probability c.
(112)
Intuitively, the label is the majority vote the second block only when parity the first block is even otherwise the label the minority vote.
44

---

Near-Optimal Decision Trees in SPLIT Second
Part 3: Bounding the Error of the Rashomon Set
We can immediately see that the best tree will achieve error 1 - The Rashomon set in this case will contain R - 1 trees (besides the empirical risk minimizer). In particular, each tree T in the Rashomon set will split one unique feature X v2d < j S 2d + R, making a prediction on an instance X (X1,....XX of the following form:
T(X) = (X1 @ x,.. + Xa.) A Majority( Majority(Xdi+11 ....)....X))
(113)
where tree T employs feature X, in its path (defined in Equation 111. Whenever X; * Xidu()) the parity of the first block will be different from that corresponding to Equation 12. However, this only happens with probability e'. For the e' proportion cases, the error will be that the best tree (i.e. at least e), giving tree T an expected accuracy of least (1 (1 - e') = - e' + O(ee).
Bounding the Performance of Greedy Tree
A greedy tree will seek split on the feature that has the highest correlation with the label y. From the defini- tion of y in Equation 1 12, it follows that ,., X2a the only variables that will have non 0 correlation with the label outcome. Thus, the tree will fully split only on these features up to depth d. However, this means that the tree does not learn the underlying parity function (X1 @ @ Xa,) Thus, - proportion of the time, the tree will achieve accuracy. +
Thus, the total accuracy is less than 1 e) + +
Theorem A.7 (LicketySPLIT Can be Arbitrarily Better than Greedy). For every O and depth budget d, there exists data distribution D and sample size n for which, with high probability over random sample S ~ DD, Algorithm 3 achieves accuracy at least 1 but pure greedy approach achieves accuracy at most +
Proof. Let x ~ Uniform ((0,) 1]2d) and
y 2 ① (2 xx) with probability - Majority(za+t).....
with probability
A purely greedy, information-gan basid splitting approach will only split on features in the Td41.... block, since all have greater than zero information gain (unlike the other variables). Such a tree can improve to at most 2 + accuracy.
However, Algorithm (LicketySPIIIT), when deciding on the first split, will pick ai as first split, after observing that being greedy from 2 onwards will achieve accuracy at least because once æ1 is known, variables 22, Fd have high information gain, and greedy tree will pick those features for splits over Ed+1, T2d- Splitting all of the first d features, then, affords performance at least 1
45

---

Near-Optimal Decision Trees in SPLIT Second
A.9. Greedy Algorithm
Algorithm 4 Greedy(D,d, X) + (Igreedy, lb)
Require: D.d,A X (Data subset, depth constraint, leaf regularization)
Ensure: !gready; lb {tree grown with greedy, CART-style method; and the objective of that tree]
1: Egreody -- (Leaf predicting the majority label D)
2: 1b < X+ (proportion of D that does not have the majority label)
3: if d' then
4: let f be the information gain maximizing split with respect to D)
5: heett Ubie + Greedy (f))) d 1)
6: Eright. lbright + Greedy(D(f).. d 1,
7:
if Uhec + right < lb then
8:
+ Ibbn + lrrigtt
9: ggreedy + tree corresponding to: if True then len, else lright
end if
11: end if
12: return fgreedy lb
A.10. RESPLIT Algorithm
Algorithm 5 RESPLITTE, D, A, dr. d)
Require: e, D. X, di, d {loss function, samples, regularizer, lookahead depth, depth budget)
1: ModifiedTTreFFRRS TreeFARMS reconfigured to get bounds (Algorithm 1) whenever it encounters subproblem
1: tf = ModiifiedTreFFARMSS. D, di) {Call ModifiedTTreFARRS with depth budget di
2: for loooaahead E i.f do {Iterate through all depth d prefixes found by Modiffed(TreeFAMMM)))
3: for leaf E Hookahead do
4: du, = depth of leaf
5:
(uu) subproblem associated with u
An = X [al (Renormalize À for the subproblem in question}
6:
7:
Tg Ly = Greedy(D(u),d du, Aa) {Objective of greedy tree trained subproblem}
8:
In TreeFARMS (D(u), du, dus Lg) {Find all subtrees with loss less than Lg}
9:
if f. is not leaf then
Replace leaf a with TreeFARMS object f. 11: end
10:
end for
Hookahead
(For each node in this prefix tree, store the number of subtrees we generate rooted at that node. This speeds up indexing)
14: end for
15: return tf {Return in-place edited ModifiedTTreFFARMS object]
A.11. Indexing Trees in RESPLIT
In this section, we present an algorithm that can quickly index trees output by RESPLIT. This would be especially useful one wishes to obtain a random sample of trees from the Rashomon set. Because Algorithm outputs a bespoke data structure involving TreeFARMS objects attached set of prefix trees, we needed devise a method efficiently query this structure locate trees at desired index.
For each prefix found by the initial ModifiedTreeFARMS call, we additionally store the number subtrees that can be formed with that prefix, Algorithm shows how this done.
46

---

Near-Optimal Decision Trees in SPLIT Second
We also store the cumulative count of the total number of trees that be formed by the prefixes seen far iterate through the list of prefixes. Algorithm called in line of Algorithm does this.
Once the cumulative count is known, we start looping over the entire Rashomon set. For the 8th index, we first obtain the corresponding prefix tree and then find the relative index of the h tree within this prefix tree structure. For example, if we query the 500 tree and our prefix contains trees indexed 400 600 in the Rashomon set, the relative index of the query tree within this prefix is 100.
Using Algorithm 8, we proceed to recursively locate the relevant subtrees beyond the prefix. In particular, at a given node in the prefix, have access the number of sub-trees that can be formed with its left and right children. We this information create two separate indexes for the left and right child (seen in lines 9 - 10)
We hash all the indexes for future retrieval (line 16 in Algorithm 9).
Algorithm 6 Tre...aRM...T.RRRMMMM........ subtrees
Require: Hookaheed (Lookahed prefix with TreeFARMS objects attached to leaves}
1: if Elookahead is None then
2: Return
3: else if foooaaeedd is a TreeFARMS object then
4: Return len((tookakcoad) !tookahead
5: end if
6: left_ exptaaxxpsss,ss, left_ jeft_subtree = www.eeerrtttttteaamssssem
7: lookahhaad-eff.chhill chw..d.noddeeeeeee. = left_subtree
8: Mookahead-lef subre, count = left expansions
9: expaassssssso subtree enumerate
10: Mookahead bhokkhhea-rrihtt.com www.tttchgglh..ooo...e = right_subtree
lookahead -inghe www.trtggggg.....eeeeee www.hhh......bree..ee
= sighteexpansoons
Return left expansions expansiios,, Hookahead (Total number of subtrees cross product of left and right
subtree count}
Algorithm 7 RESPLIITTRRE CISSPPLTT.SS..ComRRRPPPLL....
Require: RESPLIT obj (The RESPLIT object output by Algorithm 5)
1: tcount = 0 Total # trees}
2: Prounts = [] (Cumulative count of # trees beginning with given prefix}
3: for Wookakead E RESPLIT_obj do
4: Prount =
5: for leaf lookaaeead do
6: tfu TreeFARMS object fitted on subproblem Duu)
7: Scount len(tfa) (Number of subtrees found for subproblem ((n)
8: Poount Peount X Scount
9:
end for
10:
Ecount = tcount + Peount
11:
Peounts- add (dddttaaan (countt
12:
end for
return Peounts: tcount
47

---

Near-Optimal Decision Trees in SPLIT Second
Algorithm 8 get leaf subtree idx(/iookaheaad tree idx)
Require: Hookaheadd tree_idx {A lookahead prefix tree with TreeFARMS objects attached to leaves, index search within
this tree)
1: if Mookahead a Leaf then
2: return lookakeed (Directly return the leaf object]
3: else if tlookahead is a list then
4: return Hokkakead (dz) (If it's a list, return the subtree at the given index]
5: end if
6: tree +- d featuree) {Initialize an empty node}
7: left_count Hookkheeed-- weft.eefffece..eee sehiidd.sbtrre..e
{The number of subtrees that can be found rooted this node)
8: right.count fLookakead right cighhttchil..uut subtree.untt
9: right_idx tree_idx % right_count
10: left idx = tree idx // right.cooo count
11: tree.left.chin cchild_ccidddd
wwwtrueeeteetteee at allidx((1nokkaeeao left child.node, left idx)
12: tree.right.child = get_leaf htt.s//wwwrb.....i..tooo....o.oe wowatiokahhhaaa www..cchhcll..c.... right.idx)
return tree
Algorithm/ 9 RESPLIT indexing
Require: RESPLIT .obj (The RESPLIT object output by Algorithm 5}
1: hash = 9 (Dictionary to map global tree indices to tree objects}
2: Mhonnt,Poounee
FEest..T_Rset.CC Count(RSSPLL.TT. (Total number of trees and prefix-wise cumulative counts)
3: start
4: for = 0 to (Prouno) do
5: if > 0 then
6: start p counts(i 1]+1 {Start index for prefix i)
7: end if
8: end p counts[i] i] {End index for prefix i} (The i-th prefix tree}
9: Hookahead = RESPLITT _owiei/iTooppeefi_iiittttt
10: for local idx = to end start - do
11: global idx start + local idx {Absolute index of tree Rashomon set}
tree = get leaf subtree idx(tiokkaeedd local idz) (Retrieve the corresponding subtree}
13: hash[global [idx] tree
14: end for
15:
end for
16:
return hash
A. Modifications to Existing GOSDT TreeFARMS Code
In this section, we detail the main modifications we made to the existing GOSDT and TreeFARMS codebase in order to set up SPLIT, LiLLI, and RESPLIT. The algorithm components in red are the modifications note that GOSDT and TreeFARMS both call these functions. TreeFARMS does some additional poot-srocsssing of the search trie to find the set of near-optimal trees the details can be seen in (Xin et al., 2022).
48

---

Near-Optimal Decision Trees in SPLIT Second
Algorithm 10 find lookahead tree(l, D, A, di, d)
Require: f. D, A, di, d floss function, dataset, regularizer, lookahead depth, global depth budget)
1: Q 0 (priority queue}
2: G + 0 {dependency graph}
3: + [1.....I 1r fbit-vector of I's of length n}
4: < S.r..O..CEATEENNDEEEE
so. di, d, 0) froot (with depth 0)}
5: (so 0))
6: D {global dataset size
while po.lb # po.ub do
8: s, d' +Q -Qppop() {index of problem to work on)
9:
p G.find(s) {find problem to work on}
10: if p. p.ub then
11:
continue {problem already solved}
12: end if
13: (lb', ubb) t (0o, oo) {loose starting bounds}
for each feature j E [1, le] do
(st, 87) + -split(s,, D) {create children}
16:
pf FIND OR CREATE NODE di, d, d' + N,
17:
PV + FIND_OR CEDDOR_CCRR
di, d, d' + N,
18:
1D' + min(lV/ p/. l/.b- + Ib) fcreate bounds as if j were chosen for splitting}
uh' <- min(ub', pd. .ub p/.ubb
20:
end for
21:
if p.lb + Ib' or p.ub * wb' then (signal the parents if an update occurred}
22:
p.ub + min(p.ub, ub') p.lb +- min(p.ub, max(p.lb, 15')
23:
24:
for Pv G.parent(p) do (propagate information upwards]
(.push((pr.inn d' 1), priority 1)
26: end for
27: end if
28:
if p.lb 2 p.ub then
29:
continue {problem solved just ]ow]
30:
end if
31: if d' < dd then
32:
for each feature j E [1, .J do (loop, enqueue children)
33:
repeat line 14-16 {fetch of and pf in case of update)
34:
Ib' + p/ + p/.lb
35:
ub' - u/bb + p!.ub
36:
if 11/ < wb' and 11/ I p.ub then
37:
Q-push((st, d + 1), priority = =0)
38:
Q-push (sy, d + 1), priority = 0)
endi
40: end for
41: end if
42: end while
43: return G
49

---

Near-Optimal Decision Trees in SPLIT Second
Algorithm 11 FIND OR CREATE NODE(G, di, d, d'. N)
Require: G,s, di d, d', N {Graph, subproblem, lookahead depth, overall depth budget, current depth, global dataset size]
return representation of subproblem entry for s, with that subropblem being present the graph
2: if G.find(s) NULL then {p not yet in graph}
3: create node
4: p.id +- s (identify by s}
5: D(s) = Dataset associated with subproblem
6:
p.ub, p.lb -- get bounds( (+), d2, d', d, N)
7:
if p.ub - p.lb + then {If further split would lead to worse objective than the upper bound]
8:
p.lb + p.ub {no more splitting needed}
9: end if
10:
Ginsser((p) (put p in dependency graph}
11: end if
12: return G.find(s)
Algorithm 12 get bounds(D di, d', d, N) lb, ub
Require: D, di, d', d, N {support, lookahead depth, current depth, overall depth budget, global dataset size}
1: return lb, ub {Return Lower and Upper Bounds}
2: if d' di then
3: Tg = Greedy(D,d 21
4:
(T,) = Leaves in Tg
5:
(T + NN Eies 1b # (x:))
6:
lb +ta
7:
ub t
8: lb + Equivalent points bound (Lin et al., 2020) min (N E(Ew)ED [y: = 1), 1 N E(WWeD [y: = =])
9: ub
10: end if
11: return lb, ub
Algorithm 13 extract.tree(D, G, d,)
Require: D.g, di (Dataset, Dependency graph of search space, lookahead depth}
return Tree
2: (Leaf predicting the majority label in D)
3: ub + X+ (proportion of D that has the minority label)
4: if di > then
5: for feature f F F do
6: Pʃ = subproblem associated with D(f)
7:
p = subproblem associated with D())
8:
py pp pp.bb ub then
9:
fopt = f (Best Feature)
10:
ub = py.ubb uub end if
11:
12:
end for
13:
tieft = extract tree(D(ffpt). ((fopt). di 1) bright extract_tree ((Sopt): dl 1) tleft lieft Lright lright
17:
end if
18: return t
50

---

Near-Optimal Decision Trees in SPLIT Second
Algorithm 14 ModifeedGOSDT(C, D, di d)
Require: f. D. A, di, d floss function, samples, regularizer, lookahead depth, depth budget}
1: 9 find_lookahead_treer
D, X, di, d)
2: I= extract.tree(D) G, di) (Extracts the prefix of the found tree, without filling in the greedy splits}
3: return t
A.13. Additional Experimental Results
For thoroughness, we provide several additional experimental results Figures 20, 21, and 22 and Tables 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, and 17. These experimental results provide other perspectives on the loss/rumtime/pparsity tradcoff, with particular emphasis on comparisons with greedy approach.
51

---

Near- Optimal Decision Trees in SPLIT Second
gondi pusdirretintue recundee
magtree mastrec tsát
greedy
go4d
go5dt joskotodd
compas
covertype Leaves:
Leaves:
0.335
0.310
0.3000
0342
0.2975
0.260
Train Loog
Ttain
0.255
0.325
0:250
0877
0.525
0.312
0.2055
netherlnnds Leaves: 3-6
adult
hypothyroid Leaves:
0.30
Leaves:
0.24
0.20
0.37
0.03
0.34
0.00
0.22
0.32
0.22
0.32
0.35
0.1
0.24
0.03
0.00
spambase
bank
bilkee Leaves: 3-6
Leaves: 3-6
Leaves: 3-6
0.775
0.22
0.225
Train Look
0.22
0.18
0.200
6:14
0.04
0.350
0.12
Runtime (s)
Runtime
Runtime
recurss gosdt Ioorahead
murtree groudy
maporee
go5dt
compas Leaves: 7-10
covertype
Leaves:
Leaves: 7-10
0.332
0.2002
Tan
0.203
0.322
0.27
0.533
0281
netherlands
adult
hypothyroid
Leaves: 7-10
Leaves: 7-10
Leoves: 7-10
0.33
0.132
0.32
0.012
0.184
0.33
0.005
0.23
5176
0.14
spambase base
bank
bike Leaves: 7-10
Leaves: 7-10
Leaves: 7-10
0.15
0.115
0.24
0.114
0.11
0.12
0.13
2.14
0.09
5.19
0.55
2.00
0102
0.42
120
Runtime
(s)
Runtime
Figure 20. Tradcoff between train loss and runtime for all algorithms tested, for different sparsity levels (mcasured by # of Icaves in the tree). Depth Budget
52

---

Near- Sstr-ll Decision Trees in SPLIT Second
gondi recurdue g05dt Jooka fead
magtree masttrc tsdt
greedy
go4d
compas
coverrtpe Leaves:
heloc
Leaves:
6:276
6.305
Text LozS
Text Look
6,240
0.220
6.355
0.200
0.240
0.54
6245
098
0.310
netherlands Leaves:
adult Leaves:
hypothyrold Leaves:
0:37
0.34
0.33
0.22
Toxt Loss
0.22
0.29
0.10
0.24
10
spambase
bank
bike Leaves: 3-6
Leaves: 3-6
Leaves: 3-6
Tuat Lass
0.5
Runtime
Runtime (s)
Runtime
pocssrecursvve gosdt loosahead
murtree
maporee
g058t
groady
compas Leaves: 7-10
covertype
Leaves:
Leaves:
0.310
5.2300
0.202
0.210
0332
0.308
5:4455
0.226
2.150
0.264
6.225
0.200
0.330
12200
netherlands Leaves: 7-10
adult
hypothyroid Leaves: 7-10
Leaves: 7-10
0.34
0.1515
0.33
0.012
0.32
2.195
0.010
Test
0.52
0.000
0.90
6.7/
0.024
0.28
0.022
0.28
0.325
0.000
spambase Leaves: 7-10
bank
bikee Leaves: 7-10
Leaves: 7-10
0.16
0.12
0.14
0.315
0.13
0.20
2.24
0.205
0.13
0.12
0.200
0.22
9.12
0.345
10
(5)
Runtime
Figure 21. Tradcoff between test loss and runtime for all algorithms tested, for different sparsity levels (measured by # of leaves in the tree). Depth Budget
53

---

Near-Optima Decision Trees in SPLIT Second
GOSDT
SPII (ours)
UccketyPPLIT (ours)
heloc
compas
netherlands
10a
10
0.050
10²
10*
10a
10a
10a
Runtime (s)
10-1
0.030
0.300
0.325
0.325
0.30
0.35
bike
adult
covertype
0.020
10a
10a
10º
10a
10
0.010
104
10a
10a
0.000
10-1
0.15
0.20
0.25
0.30
0.175
0.200
0.225
0.250
0.275
0.21
0.26
0.28
0.30
0.32
0.34
Regularized Train Risk
Figure 22. Regularized training objective vs. training time (in scconds) for GOSDT vs. our algorithms. The size of the points indicates the number of leaves in the resulting tree. Both SPLIT and LicketySPLIT much faster for most values of sparsity penalty with the only potential slowdown being in the sub-second regime due to overhead costs. Depth Budget = 5.
Table Results for 0.001
Dataset
Algorithm
Train Objective
Runtime (s)
GOSDT (SOTA)
0.1322 + 0.0015
606.87 2.12
bike
LicketySPLIT (ours)
0.1328 0.0010
1.68 i 0.05
Greedy
0.2101 = 0.0401
0.01 + 0.00
GOSDT (SOTA)
0.1797 0.0032
372.62 2.01
adult
LicketySPLIT (ours)
0.1800 = 0.0020
1.46 + 0.01
Greedy
0.1950 = 0.0350
0.01 + 0.00
GOSDT (SOTA)
0.2442 + 0.0002
528.67 + 1.68
covertype
LicketySPLIT (ours)
0.2472 + 0.0003
11.86 + 0.29
Greedy
0.2681 0.0020
0.01 + 0.00
54

---

Near-Optimal Decision Trees in SPLIT Second
Table Results for 0.006
Dataset
Algorithm
Train Objective
Runtime (s)
GOSDT
0.3107 = 0.0128
266.15 + 1.81
heloc
SPLIT (ours)
0.3107 = 0.0128
5.06 0.32
LicketySPLIT (ours)
0.3107 + 0.0128
0.46 + 0.01
GOSDT
0.3473 + 0.0029
8.99 0.31
compas
SPLIT (ours)
0.3473 + 0.0029
0.64 + 0.01
LicketySPLIT (ours)
0.3473 = 0.0029
0.29 = 0.00
GOSDT
0.3156 + 0.0006
70.49 + 0.15
netherlands
SPLIT (ours)
0.3165 + 0.0008
2.29 + 0.01
LicketySPLIT (ours)
0.3165 + 0.0008
0.61 + 0.00
GOSDT
0.1736 = 0.0007
607.32 + 0.89
bike
SPLIT (ours)
0.1737 = 0.0072
13.77 = 0.18
LicketySPLIT (ours)
0.1753 = 0.0158
1.64 = 0.01
GOSDT
0. 0.1998 + 0.0010
264.79 + 0.99
adult
SPLIT (ours)
0.1998 + 0.0010
4.89 0.02
LicketySPLIT (ours)
0.1998 = 0.0010
1.39 = 0.00
GOSDT
0.2652 + 0.0001
32.27 = 0.27
covertype
SPLIT (ours)
0.2652 + 0.0001
6.21 + 0.02
LicketySPLIT (ours)
0.2652 + 0.0001
11.24 + 0.01
Table 9. Results for = 0.011
Dataset
Algorithm
Train Objective
Runtime (s)
GOSDT
0.3214 + 0.0017
231.41 5.55
heloc
SPLIT (ours)
0.3214 + 0.0017
4.10 = 0.03
LicketySPLIT (ours)
0.3214 + 0.0017
0.44 + 0.00
GOSDT
0.3621 = 0.0066
7.17 0.53
compas
SPLIT (ours)
0.3621 = 0.0066
0.32 0.08
LicketySPLIT (ours)
0.3621 = 0.0066
0.26 0.01
GOSDT
0.3406 + 0.0006
56.54 = 0.11
netherlands
SPLIT (ours)
0.3515 = 0.0105
1.74 = 0.01
LicketySPLIT (ours)
0.3515 = 0.0105
0.60 = 0.00
GOSDT
0.1961 = 0.0006
610.20 + 0.55
bike
SPLIT (ours)
0.1961 = 0.0006
12.91 = 0.05
LicketySPLIT (ours)
0.1961 + 0.0006
1.60 + 0.01
GOSDT
0.2148 = 0.0010
211.86 0.68
adult
SPLIT (ours)
0.2148 = 0.0010
2.90
LicketySPLIT (ours)
0.2148 = 0.0010
1.39
GOSDT
0.2752 + 0.0001
2.62
covertype
SPLIT (ours)
0.2752 + 0.0001
6.07 + 0.08
LicketySPI.IT (ours)
0.2752 + 0.0001
10.70 + 0.00
55

---

Near-Optimal Decision Trees in SPLIT Sccond
Binarization Time (s)
Dataset
Algorithm
Runtimes (s)
Test Loss
LicketySPLIT (ours)
[2.85, 2.97]
[0.306, 0.328]
compas
[2.69, 2.91]
SPLIT (ours)
[2.84, 3.01]
[0.314, 0.335]
CART
[0.00, 0.00]
[0.322, 0.354]
LicketySPLIT (ours)
[0.47, 0.52]
[0.103, 0.119]
bank
[0.37, 0.41]
SPLIT (ours)
[0.57, 0.67]
[0.101, 0.116]
CART
[0.00, 0.00]
[0.106, 0.123]
LicketySPLIT (ours)
[2.67, 2.81]
[0.133, 0.147]
bike
[2.20, 2.32]
SPLIT (ours)
[3.80, 4.71]
[0.139, 0.152]
CART
[0.01, 0.01]
[0.207, 0.215]
LicketySPLIT (ours)
[2.94, 3.19]
[0.155, 0.159]
adult
[2.26, 2.74]
SPLIT (ours)
[3.66, 4.26)
[0.155, 0.159|
CART
[0.02, 0.02]
[0.183, 0.191]
LicketySPLIT (ours)
[1.13, 1.30]
10.004, 0.005]
hypothyroid
[0.99, 1.32]
SPLIT (ours)
[1.18, 1.36]
[0.004, 0.005]
CART
[0.00, 0.00]
[0.009, 0.014]
LicketySPLIT (ours)
[25.50, 25.75]
[0.242, 0.244]
covertype
[19.49, 20.00]
SPLIT (ours)
[25.62, 25.91]
[0.242, 0.244]
CART
[0.68, 0.69)
[0.266, 0.269)
LicketySPLIT (ours)
[2.31, 2.39]
[0.285, 0.294]
netherlands
[1.92, 2.04]
SPLIT (ours)
[2.74, 3.06]
[0.284, 0.294]
CART
[0.00, 0.00)
[0.314, 0.338)
LicketySPLITT (ours)
[1.20, 1.27]
[0.284, 0.289]
heloc
[0.89, 1.01]
SPLIT (ours)
[2.08, 2.53]
[0.284, 0.289]
CART
[0.01, 0.01]
[0.293, 0.299]
LicketySPLIT (ours)
[0.88, 0.90]
[0.094, 0.114]
spambase
[0.70, 0.73]
SPLIT (ours)
[1.16, 1.19]
[0.097, 0.111]
CART
[0.01, 0.01]
[0.164, 0.207]
Table Results (# leaves between 6). 95% confidence interval is shown. Binarization only applicable to LicketySPLIT/SPLIT.
The runtimes for SPLIT LicketySPLIT include binarization time.
56

---

Near-Optimal Decision Trees in SPLIT Sccond
Binarization Time (s)
Dataset
Algorithm
Runtimes (s)
Test Loss
LicketySPLIT (ours)
[2.86, 2.98]
[0.303, 0.321]
compas
[2.69, 2.91]
SPLIT (ours)
[2.91, 3.06]
[0.302, 0.320]
CART
[0.00, 0.00]
[0.325, 0.338]
LicketySPLIT (ours)
[0.48, 0.53]
[0.103, 0.118]
bank
[0.37, 0.41]
SPLIT (ours)
[0.59, 0.68]
[0.101, 0.117]
CART
[0.00, 0.00]
[0.106, 0.123]
LicketySPLIT (ours)
[2.70, 2.84]
[0.123, 0.125]
bike
[2.20, 2.32]
SPLIT (ours)
[4.06, 4.78]
[0.127, 0.134]
CART
[0.01, 0.01]
[0.166, 0.238)
LicketySPLIT (ours)
[2.97, 3.22]
[0.149, 0.154]
adult
[2.26, 2.74]
SPLIT (ours)
[3.95, 4.54]
[0.149, 0.155]
CART
[0.03, 0.04]
[0.165, 0.180J
LicketySPLIT (ours)
[1.13, 1.30]
[0.003, 0.005]
hypothyroid
[0.99, 1.32]
SPLIT (ours)
[1.20, 1.38)
[0.003, 0.005]
CART
[0.00, 0.00]
[0.002, 0.004]
LicketySPLIT (ours)
[25.50, 25.74]
[0.240, 0.243]
covertype
[19.49, 20.00]
SPLIT (ours)
[26.57, 26.92]
[0.239, 0.242]
CART
[0.99, 1.00)
[0.254, 0.256)
LicketySPLIT (ours)
[2.31, 2.41]
[0.282, 0.293]
netherlands
[1.92, 2.04]
SPLIT (ours)
[2.79, 3.12]
[0.282, 0.293]
CART
[0.00, 0.00)
[0.297, 0.314]
LicketySPLITT (ours)
[1.21, 1.27]
[0.284, 0.293]
heloc
[0.89, 1.01]
SPLIT (ours)
[2.18, 2.42]
[0.282, 0.293]
CART
[0.00, 0.00]
[0.291, 0.327]
LicketySPLIT (ours)
[0.89, 0.91]
[0.085, 0.096]
spambase
[0.70, 0.73]
SPLIT (ours)
[1.36, 1.52]
[0.085, 0.098]
CART
[0.02, 0.02]
[0.114, 0.141]
Table Results (# leaves between 7-10). 95% confidence interval shown. Binarization only applicable to LicketySPLIT/SPLIT.
The runtimes for SPLIT / LicketySPLIT include binarization time.
57

---

Near-Optimal Decision Trees in SPLIT Sccond
Binarization Time (s)
Dataset
Algorithm
Runtimes (s)
Test Loss
SPLIT (ours)
[2.92, 3.08]
[0.302, 0.316]
compas
[2.69, 2.91]
CART
[0.00, 0.00]
[0.318, 0.333)
LicketySPLIT (ours)
[0.49, 0.53]
[0.099, 0. 0.116]
bank
[0.37, 0.41]
SPLIT (ours)
[0.59, 0.69]
[0.100, 0.118)
CART
[0.00, 0.00]
[0.104, 0.1
LicketySPLIT (ours)
[2.70, 2.83]
[0.114, 0.123]
bike
[2.20, 2.32]
SPLIT (ours)
[4.40, 5.14]
[0.121, 0.129]
CART
[0.02, 0.02]
[0.130, 0.139]
LicketySPLIT (ours)
2229,,3.22
[0.148, 0.155]
adult
[2.26, 2.74]
SPLIT (ours)
[4.09, 4.79]
[0.148, 0.154]
CART
[0.04, 0.04)
[0.154, 0.161]
LicketySPLIT (ours)
[2.32, 2.42]
[0.283, 0.291]
netherlands
[1.92, 2.04]
SPLIT (ours)
[2.89, 3.22]
[0.282, 0.291]
CART
[0.00, 0.00]
[0.293, 0.309]
LicketySPL.IT (ours)
[1.23, 1.29]
[0.281, 0.292]
heloc
[0.89, 1.01]
SPLIT (ours)
[2.41, 2.73]
[0.286, 0.297]
CART
[0.02, 0.02]
[0.298, 0.306]
LicketySPLIT (ours)
[0.89, 0.92]
[0.086, 0.094]
spambase
[0.70, 0.73]
SPLIT (ours)
[1.50, 1.65]
[0.081, 0.093]
CART
[0.02, 0.02]
[0.1 14, 0.136]
Table 12. Results (# leaves between 11-14). The 95% confidence interval is shown. Binarization only applicable to LicketyS- PLIT/SPLIT. The runtimes for SPLIT / LicketySPLIT include binarization time.
58

---

Near-Optimal Decision Trees in SPLIT Second
Binarization Time (8)
Leaves
Dataset
Algorithm
Runtimes (s)
Test Loss
(95% CT)
LicketySPLIT (ours)
[14.2, 17.2]
[2.99, 3.23]
[0.305, 0.325]
compas
[2.69, 2.91]
SPLIT (ours)
[13.6, 16.0)
[2.76, 3.32]
[0.304, 0.314]
CART
[28.6, 30.8]
[0.00, 0.00]
[0.307, 0.324]
LicketySPLIT (ours)
[20.2, 23.8]
[0.52, 0.57]
[0.102, 0.116]
bank
[0.37, 0.41]
SPLIT (ours)
[15.2, 16.0]
[0.63, 0.75]
[0.102, 0.118]
CART
[16.6, 17.8)
[0.01, 0.01)
[0.098, 0.112]
LicketySPLIT (ours)
[17.8, 19.6]
[2.72, 2.94]
[0.114, 0.122]
bike
[2.20, 2.32]
CART
[27.6, 28.2]
[0.02, 0.03]
[0.122, 0.130]
LicketySPLIT (ours)
[19.8, 21.4]
[2.90, 3.36]
[0.146, 0.151]
adult
[2.26, 2.74]
SPLIT (ours)
[15.2, 16.0)
[4.29, 5,45]
[0.148, 0.153]
CART
[22.6, 23.2)
[0.02, 0.03)
[0.152, 0.157]
LicketySPLIT (ours)
[15.4, 18.4]
[2.33, 2.72]
[0.282, 0.291]
netherlands
[1.92, 2.04]
SPLIT (ours)
[13.4, 15.2]
[2.97, 3,45]
[0.284, 0.291]
CART
[18.6, 20.2]
[0.01, 0.01]
[0.293, 0.306]
LicketySPLIT (ours)
[18.0, 23.0]
[1.25, 1.44]
[0.285, 0.295]
heloc
[0.89, 1.01]
SPLIT (ours)
[14.4, 16.4]
[2.31, 2.63]
[0.286, 0.301]
CART
[21.4, 23.2]
[0.02, 0.02]
[0.290, 0.299]
LicketySPLIT (ours)
[24.4, 25.6]
[0.91, 0.96]
[0.081, 0.088]
spambase
[0.70, 0.73]
SPLIT (ours)
[14.0, 15.8)
[1.46, 1.57]
[0.081, 0.093]
CART
[20.0, 23.2]
[0.02, 0.02]
[0.082, 0.103]
Table 13. Comparing CART and SPLIT/LicketySPLIT for sparse The 95% confidence interval is shown. Binarization is only applicable to LicketySPLITSSPIIT. The runtimes for SPLIT LicketySPLIT include binarization time. We report the best tree with between 15 30 leaves found during hyperparameter search.
Dataset
Leaves
Runtimes
Losses
bank
[20.20, 23.80]
[0.52, 0.56]
[0.102, 0.116]
bike
[17.80, 19.60]
[2.80, 2.92]
[0.114, 0.122]
adult
[19.80, 21.40]
[3.18, 3.40]
[0.146, 0.151]
netherlands
[15.40, 18.40]
[2.34, 2.43]
[0.282, 0.292]
heloc
[18.00. 23.00]
[1.24, 1.30]
[0.286, 0.295]
spambase
[24.40, 25.60]
[0.88, 0.91]
[0.081, 0.088]
Table 14. SPLIT/LicketySPLIT for non-sparse trees. For this variant, we set À = 1e - 5 and ran our algorithms over 5 trials. We show the 95% confidence interval. This shows that algorithms are capable producing non-sparse trees. We may prefer do this practice if there are interpretability constraints or if we can get well performing model with much fewer than 20 leaves.
59

---

Near-Optimal Decision Trees in SPLIT Second
Dataset
Algorithm
Runtimes (s)
Test Loss
CART (with binary features)
[0.00, 0.00]
[0.325, 0.352]
compas
CART (with cont features)
[0.00, 0.00]
[0.322, 0.354]
CART (with binary features)
[0.00, 0.00]
[0.106, O. 0.1
bank
CART (with cont features)
[0.00, 0.00]
[0.106, 0.123]
CART (with binary features)
[0.02, 0.03]
[0.208, 0.215]
bike
CART (with cont features)
[0.208, 0.215]
CART (with binary features)
0.01]
[0.168, 0.197]
adult
CART (with cont features)
[0.02, 0.02]
[0.183, 0.191]
CART (with binary features)
[0.00, 0.00]
[0.009, 0.014]
hypothyroid
CART (with cont features)
[0.00, 0.00]
[0.009,
CART (with binary features)
[0.06, 0.07]
[0.253, 0.256]
covertype
CART (with cont features)
[0.68, 0.69]
[0.266, 0.269]
CART (with binary features)
10.01, 0.01]
[0.332, 0.342]
netherlands
CART (with cont features)
[0.00, 0.00]
[0.314, 0.338]
CART (with binary features)
[0.01, 0.01]
[0.293, 0.299]
heloc
CART (with cont features)
[0.01. 0.01]
[0.293, 0.299]
CART (with binary features)
10.00, 0.00]
[0.156, 0.208]
spambase
CART (with cont features)
[0.01, 0.01]
[0. (0.164, 0.207]
Table 15. Comparison between CART (with binary features) and CART (with cont features) for trees with 3-6 leaves. The 95% confidence interval is shown.
Dataset
Algorithm
Runtimes (s)
Test Loss
CART (with binary features)
[0.00, 0.00]
[0.3197, 0.3388]
compas
CART (with cont features)
[0.00, 0.00]
[0.3253, 0.3385]
CART (with binary features)
[0.00, 0.00]
[0.1109, 0.1193]
bank
CART (with cont features)
[0.00, 0.00]
[0.1061, 0. 0.1227]
CART (with binary features)
0.011,0.111
[0.1718, 0.1911]
bike
CART (with cont features)
[0.00, 0.01]
[0.1661, 0.2380]
CART (with binary features)
[0.02, 0.02]
[0.1647, 0.1803]
adult
CART (with cont features)
[0.03, 0.04]
[0.1647, O. 0.1803]
CART (with binary features)
[0.00, 0.00]
[0.0030, 0.0053]
hypothyroid
CART (with cont features)
[0.00, 0.00]
[0.0015, 0.0042]
CART (with binary features)
[0.07, 0.07]
[0.2501, 0.2557]
covertype
CART (with cont features)
[0.99, 1.00]
[0.2540, 0.2560]
CART (with binary features)
[0.01, 0.01]
[0.3323, 0.3590]
netherlands
CART (with cont features)
[0.00, 0.00]
[0.2966, 0.3137]
CART (with binary features)
[0.00, 0.00]
[0.2895, 0.3015]
heloc
CART (with cont features)
[0.01, 0.01]
[0.2926. 0.2990]
CART (with binary features)
[0.00, 0.00]
[0. 1001 O. 1,047 [0.1 0.1409]
spambase
CART (with cont features)
[0.02. 0.02]
Table 16. Comparison between CART (with binary features) and CART (with cont features) for trees with 7-10 leaves. The 95%
confidence interval is shown.
60

---

Near-Optimal Decision Trees in SPLIT Second
Dataset
Algorithm
Runtimes (s)
Test Loss
CART (with binary features)
[0.00, 0.00]
[0.3179, 0.3334]
compas
CART (with cont features)
[0.00, 0.00]
[0.3176, 0.3334]
CART (with binary features)
[0.00, 0.00]
10.1087, O. 1.76
bank
CART (with cont features)
[0.00, 0.00]
[0.1045, O. 0.1193]
CART (with binary features)
[0.04, 0.05]
[0.1288, 0.1354]
bike
CART (with cont features)
[0.02, 0.02]
[0.1296, O. 031887]
CART (with binary features)
[0.02, 0.03]
[0.1543, 0.1615]
adult
CART (with cont features)
[0.04, 0.04]
[0.1542. 0.1615]
CART (with binary features)
[0.00, 0.00]
[0.0045, 0.0083]
hypothyroid
CART (with cont features)
[0.00, 0.00]
[0.0023, 0.0045]
CART (with binary features)
[0.07, 0.07]
[0.2485, 0.2537]
covertype
CART (with cont features)
[1.22, 1.23]
[0.2529, 0.2554]
CART (with binary features)
[0.01, 0.01]
[0.3021, 0.3115]
netherlands
CART (with cont features)
[0.00, 0.00]
[0.2934, 0.3090]
CART (with binary features)
[0.01, 0.01]
[0.2961, 0.3047]
heloc
CART (with cont features)
[0.02, 0.02]
[0.2983, 0.3057]
CART (with binary features)
[0.01, 0.01]
10.1064, 0. 0.1416]
spambase
CART (with cont features)
[0.02, 0.02]
[0. 144, 0.1359]
Table 17. Comparison between CART (with binary fcatures) and CART (with cont features) for trees with 1 11-14 leaves. The 95%
confidence interval is shown.
61

---

Near-Optimal Decision Trees in SPLIT Second
A.14. Predictive Multiplicity of our Rashomon Set
We illustrate another metric showing the approximation ability of RESPLIT. For each example in the training set, computed the variance in predictions across models in the Rashomon The distribution of this variance over training examples is shown box plot for each dataset. Figure 23 and Table 18 shows that there is minimal empirical difference in the predictive multiplicity of original vs RESPLIT Rashomon sets.
Variance in Predictions: Original RESPLIT Rashomon Sets
0.24
Variance in Predictions
0.22
0.20
0.18
Original Rashomon Set RESPLIT Rashomon Set
bike
netherlands
hiv
compas
heloc
spambase
Dataset
Figure Illustration of the predictive multiplicity original and RESPLIT Rashomon Sets. 0.02, = 0.01, Depth Budget
5, Lookahead depth 3.
Mean Variance (Original Rashomon Set)
Mean Variance (RESPLIT)
Dataset
+ Std Dev
Std Dev
bike
0.2464 0.0023
0.2458 0.0024
netherlands
0.2017 = 0.0190
0.2187 = 0.0122
hiv
0.2485 + 0.0018
0.2478 + 0.0027
compas
0.2389 + 0.0138
0.2407 + 0.0149
heloc
0.2419 + 0.0081
0.2419 + 0.0081
spambase
0.2359 = 0.0055
0.2284 + 0.0037
Table 18. Illustration of the predictive multiplicity the original and RESPLIT Rashomon Sets. 0.02, = 0.01, Depth Budget 5,
Lookahead depth 3. This presents results in Figure in tabular form.
62


Reviews:
[{"review_id": "XY0B2Kj3Vq", "reviewer": "Reviewer_KacM", "summary": "Authors propose a decision tree learning method fast like greedy trees and precise like optimal ones. For that they call an optimal solvers only for some subtrees during construction of the overall tree. The paper is well-explained and well-written. Topic is important. The claims are not supported properly by experiment which we discuss next.\n\n## Update after rebuttal\nWhile I still believe SPLIT will not be used in practice to do machine learning, i.e, by industry or education to compute trees that generalize well to unseen data, the authors did a good job to answer my questions during the rebuttal. Indeed, I am not conviced that SPLIT will scale better than purely optimal decision trees like claimed by the authors as no significant benchmarking of SPLIT against CART was performed on big datasets and or deep trees. But the paper might be of interest for the optimal trees community, albeit smaller than the whole ICML community. Hence I would not mind this paper to be accepted and I will still praise the authors for the clarity of the work and the hard work during the rebuttal. Let objectivity triumph over subjectivity and make ICML better.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Your core concerns seem to focus on handling continuous features, number of repetitions, and showing results with training objective. We address those points in detail below. In brief, our method is fully compatible with continuous features, our results are robust to (even more) multiple repetitions, and we have an excellent tradeoff between training objective and runtime.\n\nRequested figures/results can be found here: https://rb.gy/5w970v\n\n**Continuous features**\n\nOur method is fully compatible with continuous features. In this work, we start off with datasets with continuous features, and binarize scalably, using a method with provable guarantees on the performance of a downstream model and demonstrated practical benefit ([1]). Separating a decision tree algorithm into two steps, a binarization step and an optimization step, is a standard approach for non-greedy decision tree optimization (see, for example, [2,3]).\n\n**Further Repetitions**\n\nWe originally ran experiments with 3 trials in Figures 3, 4, 5, and 6. The error bars correspond to the 95% CI obtained (i.e., 1.96x standard error). In the linked figures above, we’ve added results over 5 seeded trials. We do a random 80/20 train-test split for each trial.\n\n**Regularized Train Loss**\n \nWe’ve redone Figure 2 of our paper with regularized train loss - showing the same benefits as the test loss (see Figure 3 in https://rb.gy/5w970v). Tables 1-3 in that link present some of same results in tabular form for clarity, showing our method is very close to optimal (GOSDT) in regularized training loss while being much faster. Figure 1 in the link also shows training loss for many methods.\n\n**Greedy vs (Lickety)SPLIT**\n\nNote from figures 1 and 2 in https://rb.gy/5w970v that we see a consistent benefit in runtime and performance for both training and test losses. These results do hold up in our main paper figures - greedy is sometimes within the red square, but rarely, if ever, performing equivalently on loss. \n\nYou asked us to describe when we would use SPLIT instead of CART - our answer, based on these plots, is \"Always!\". We’re substantially outperforming greedy methods. Even in the worst case on these real world datasets, we achieve accuracy comparable to CART with a runtime of about a second, so there is minimal cost to using our approach – no disadvantage at all.\n\n**Scalability**\n\nThese distinct implementations are not quite as distinct as they may seem - MurTree, MAPTree, GOSDT, and DL8.5 all use python wrappers of C++ implementations. Cython is a python wrapper around C.\nWe also note that there should be no concerns about the comparison between GOSDT and SPLIT, since SPLIT uses a modified version of GOSDT’s code.\n\nNote that our scalability claims are thoroughly theoretically justified, with further details in section 5 of the main paper as well as the Appendix. For example, we prove LicketySPLIT is a polynomial-time algorithm, whereas optimal trees are NP-hard.\n\nThe number of calls to a greedy solver would be a metric unique only to SPLIT and LicketySPLIT, and none of the other algorithms we compared against. We’ve never seen a paper use that metric since it doesn’t actually measure run time fairly across algorithms. It is unfortunately not a suitable metric to facilitate comparison with other algorithms.\n\n**Additional Points**\n \n>Could you compute optimal splits close to the root with some other optimal algorithm than GOSDT?\n\nWe can! One of our approach’s advantages is that you can indeed compute optimal splits up to the lookahead depth using a different optimal algorithm than GOSDT. The adjustments to SPLIT remain quite simple for any dynamic programming based approach.\n\n>Could you please explain why rashomon sets are useful for decision tree algorithms ?\n\nRashomon sets are useful whenever we want to understand a set of many alternative models that are all almost identically performant. Please see [4] for an approachable review of some of the many benefits of this approach.\n\n>I recommend using the benchmark from Grinsztajn et al., 2022\n\nFigure 4 in https://rb.gy/5w970v shows results for the largest classification dataset in that benchmark. We are happy to add even further experiments on more datasets.\n\n[1] McTavish, H., Zhong, C., Achermann, R., Karimalis, I., Chen, J., Rudin, C., & Seltzer, M. (2022). Fast Sparse Decision Tree Optimization via Reference Ensembles. AAAI, 36(9), 9604-9613\n\n[2] Lin, J., Zhong, C., Hu, D., Rudin, C., & Seltzer, M. (2020). Generalized and Scalable Optimal Sparse Decision Trees. ICML, 119, 6150–6160.\n\n[3] Demirović, E., Lukina, A., Hebrard, E., Chan, J., Bailey, J., Leckie, C., Ramamohanarao, K., & Stuckey, P. J. (2022). MurTree: Optimal decision trees via dynamic programming and search. JMLR, 23(26), 1–47.\n\n[4] Rudin, C., Zhong, C., Semenova, L., Seltzer, M., Parr, R., Liu, J., Katta, S., Donnelly, J., Chen, H., & Boner, Z. (2024). Position: Amazing things come from having many good models. ICML, 1742, 1–13.", "claims_and_evidence": "You claim near optimality which makes sense from how you construct your tree. However you don't show it in practice. I do not see any figure with (regularized) train loss in the main paper.\n\nYou claim speed/scalability (lower complexity than fully optimal approaches hence can be used for bigger problems). It is hard for me to say you support that claim. First the train time is measured in seconds. Baselines that you compare have different implementations, e.g. the greedy tree is in cython while murtree is in C. It would be better for you to measure the speed as a function of calls to a greedy solver during construction of the tree. Hence you could fairly compare speed. \nFurthermore, looking at the red squared figures in Figure 3 and 4; I only see 2 datasets (Bank and Netherlands) where both (Lickety) SPLIT is the fastest non-greedy algorithm and the greedy tree is not in the red square. \nOverall, adding the fact that SPLIT requires binary features, I am not convinced by your experiments that SPLIT is a useful algorithm. As I dont see a clear trend of SPLIT have both a better loss than CART and a better speed than Optimal trees. \n\nI would also recommend that you do multiplte train/test split repetitions in your experiment to make them more significant and that you write what the error bars are. \n\nI think claiming interpretability does not bring much to your contribution I like more the fact that you attempt to brdige the gap between greedy and optimal trees. \n\nI did not check any claims regarding rashomon sets.", "methods_and_evaluation_criteria": "I checked the proposed method and evaluation criteria.Method is sound and somewhat original (optimal splits up to depth d<D the greedy from d to D). Datasets chosen for evaluation are big enough. A weak point is that the method is limited to binary features. \nI don't think those red squared boxes bring anything. Just make a plot of single points (one for each algo) on the loss-speed frontier.", "theoretical_claims": "I did not check theroretical claim.", "experimental_designs_or_analyses": "I spent most of my time after understanding SPLIT to review the experiment sections. I read all of them in the main paper and in the Appendix, and in the code. \n\nThe experiments are weak:\nNo multiple repetitions of experiments, no multiple train/test splits no explanation of error bars no cross validation. \n\nWhen proposing a new tree algorithm, I recommend using the benchmark from Grinsztajn et al., 2022: Why do tree-based models still outperform deep learning on tabular data?", "relation_to_broader_scientific_literature": "This works bridges the gap between optimal and greedy trees. They cover well both literatures. They even mention a very similar work (Top N from Blanc. 2024) which also develops a new heuristic tree algorithm with better accuracy than greedy trees and better speed than optimal trees. Hence this work is perfectly situated in the current literature. \n\nI think the authors did an amazing job situating their work. And I liked the little teaser figure 1 a lot.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "In the contribs you write:\n\"We theoretically prove that our algorithms scale exponentially faster in the number of features than optimal decision\ntree methods\" I guess you wanted to say \"slower\".", "questions_for_authors": "Could you do more straight to the point plots with multiple train/test splits ? Just plot the loss - speed trade-off of the different tree algorithms. You can do five subplots, each one with a different sparsity value. \n\nCould you redo figure 2 with train accuracy ? If you claim \"optimality\" it is essential.\n\nWhy or when would someone use SPLIT over CART ?\n\nCould you compute optimal splits close to the root with some other optimal algortihm than GOSDT ?\n\nI am unfamiliar with rashomon sets so I did not review most of the related contribution. I hope I did not miss something key. Could you please explain why rashomon sets are useful for decision tree algorithms ?\nIn the meantime I believe you did not perform serious enough experiments and the lack of compatibility with continuous features is a strong limitation for SPLIT to ever be used in practice. \n\nThe work is still good and original but more straightforward experiments focusing on train/test loss with respect to speed with multiple repetitions are for me necessary for this paper to be accepted", "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": "", "extra_scores": {}}, {"review_id": "64D4YoR7zW", "reviewer": "Reviewer_2Fk5", "summary": "This paper proposes a decision-tree search method for producing near-optimal decision trees in an efficient way. The authors use a look-ahead mechanism to quickly evaluate tree candidates. The authors demonstrate their method in terms of loss, runtime, and Rashomon set search accuracy.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Question 1 (How does the distribution of data affect the runtime of the method)**\n\nWe’ve given standard worst-case runtime analysis in our theory section, which gives the worst case runtime even for adversarial data distributions. Even for an adversarial dataset that requires high tree complexity (i.e. a noiseless sine wave over a single continuous feature), our method is a substantial improvement to existing optimal tree methods that struggle to scale to larger depths.\n\nIt seems like this is a question about decision trees’ theoretical benefits as a model class under adversarial distributions. This question is out of scope for our work, which is about improving performance for real-world datasets relative to other decision tree approaches. We’re happy to discuss related work on trees’ ability to achieve performance comparable to other model classes (such as [1], which shows trees match other model classes’ performance when there is noise in labels), but our work’s primary contribution is an improvement targeting the specific model class of trees.\n\n**Question 2 (random retraining vs RESPLIT)**\n\nOur understanding is that you’re asking about how RESPLIT compares to an alternative approach that uses random resampling of data, then runs decision tree learning methods on these samples. Is that correct? If so, please see below.  \n\nWe draw inspiration from the original paper on enumerating the entire Rashomon set for decision trees [2]. Figure 1 of that paper shows a comparison with this proposed resampling method, and demonstrates that it rarely creates models in the Rashomon set. It also leaves much of the Rashomon set unexplored. We show that the models we find are consistently within the true Rashomon set (see for example the precision result in table 2).\n\nBased on your question, it also seems like you may be asking how close the models we find are to optimal, relative to that resampling approach. Certainly the best models in our approximate Rashomon set are almost exactly the same as the best models in the true Rashomon set - since RESPLIT always includes the SPLIT tree in its set of models, and we’ve shown earlier in the paper that the SPLIT tree is regularly comparable to the objective of the best possible tree (see also the training objective results in our response to reviewer KaCM).\n\nIf there’s another baseline you had in mind when you mention RETRAIN, please do let us know!\n\n**Question 3 (Predictive Multiplicity)**\n\nHere are some results on predictive multiplicity: https://rb.gy/axzek9. For each example in the training set, we’ve computed the variance in predictions across models in the Rashomon set. The distribution of this variance over training examples is shown as a box plot for each dataset. We see that RESPLIT exhibits similar predictive multiplicity as models in the original Rashomon set. This is yet another metric showing the approximation ability of RESPLIT.\n\n> Aspects that are typical in the Rashomon analysis are also relevant in a heuristic Rashomon search: predictive multiplicity and other variance measures, etc.\n\nWe evaluate predictive multiplicity above, but to address your comment about other Rashomon set evaluations, we’d like to draw your attention to the evaluation we’ve done in Table 1, which shows our Rashomon Set approximation’s ability to help in downstream variable importance tasks. The Rashomon Importance Distribution computed on the full Rashomon set gives almost identical variable importance rankings to the Rashomon Importance Distribution computed on the RESPLIT Rashomon set sample (with rank correlation near or matching the best possible result of 1.0). The full results can be seen in Figure 16 in the Appendix.\n\n\n[1] Semenova, L., Chen, H., Parr, R., & Rudin, C. (2023). A path to simpler models starts with noise. Advances in neural information processing systems, 36, 3362-3401.\n\n[2] Xin, R., Zhong, C., Chen, Z., Takagi, T., Seltzer, M., & Rudin, C. (2022). Exploring the whole rashomon set of sparse decision trees. Advances in neural information processing systems, 35, 14071-14084.", "claims_and_evidence": "Overall, the claims are straightforward. As they discover a near-optimal model wrt accepted Rashomon criteria, and can evaluate this near optimality wrt runtime.The two main figures, and Table 1 support their efficiency claims well.", "methods_and_evaluation_criteria": "The method is clever and very effective, empirically. The authors achieve a 100x speed-up in some applications.", "theoretical_claims": "The main analytical results are somewhat light, as (in my estimation) this is largely an applied and practical paper.", "experimental_designs_or_analyses": "The evaluation is straightforward. There are some qualitative results in line with prior work on Rashomon sets that would fit well for their model, i.e. to understand whether it produces a biased sampling (in the data sense, not the demographic sense) of models in the Rashomon set. This to me is frankly more interesting than runtime.", "relation_to_broader_scientific_literature": "This work is a very significant contribution in the work on optimal (or near optimal) decision trees.", "essential_references_not_discussed": "No suggestions", "other_strengths_and_weaknesses": "Overall, this work is very strong, within the specific area of optimal decision trees. One might criticize the scope of the work as niche or decision trees are too simple or outmoded. For readers who value this research area (as I do), the practical value of this paper in applications requiring maximal interpretability is very high. \n\nOne weakness is a lack of (analytically) characterizing the loss in *near* optimality (vs. optimality), and a better result for this tradeoff of optimality vs. runtime (e.g. maybe in an anytime paradigm.)\n\nMore generally, I think the authors focus too much on efficient near-optimality wrt runtime rather than the analytical (or empirical) results around the set of trained models over the search. Aspects that are typical in the Rashomon analysis are also relevant in a heuristic Rashomon search: predictive multiplicity and other variance measures, etc.", "other_comments_or_suggestions": "Covered above.", "questions_for_authors": "1. How does the distribution of data affect the runtime of the method? One might imagine a distribution that's easy for a GLM, or some kernel function to fit, but for example, requires a deep decision tree. i.e. the fit may be near-optimal, but the optimal tree over the class of decision trees still isn't a great model. Do you have some results in these worst-cases wrt data distribution/high tree complexity?\n\n2. Are there real applications for which random retraining for Rashomon estimation are prohibitive but this method isn't? That is, if I can use random resampling to achieve a model in the Rashomon set, the proposed method only seems to meet this rashomon threshold (empirically) more efficiently. It doesn't, for example, achieve a stricter Rashomon threshold than retraining is likely to achieve (i.e. \"nearer-optimal\" than RETRAIN)?. \n\n3. Do you have results for the predictive multiplicity in the set of models trained by the proposed method? Are these models of higher/lower variance than the Rashomon set? \n.", "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": "", "extra_scores": {}}, {"review_id": "qyQ8QFLPF5", "reviewer": "Reviewer_QmXu", "summary": "The paper introduces a family of algorithms called SPLIT (SParse Lookahead for Interpretable Trees) for decision tree optimization. These algorithms aim to bridge the gap between the scalability of greedy methods and the accuracy of optimal decision tree methods. The key idea is to use dynamic programming with branch and bound up to a shallow \"lookahead\" depth, and then switch to greedy splitting. The authors also extend their algorithm to approximate the Rashomon set of decision trees.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The \"Blossom: An Anytime Algorithm for Computing Optimal Decision Trees\" paper by Demirović et al. (2023) is a relevant work that is not cited or discussed in the submission. Both papers address the challenge of finding optimal decision trees, with a focus on improving scalability and finite-time performance. Demirović et al. (2023) propose an anytime algorithm (Blossom) based on dynamic programming, which shares similarities with the SPLIT approach in terms of aiming for efficiency and anytime behavior. A comparison with Blossom would have strengthened the paper.\n\nThank you for mentioning Blossom. We’re glad to add a discussion of this work to the paper, and we agree it should be cited - it's an interesting and distinct approach from our own. We’re confident incorporating Blossom does not change the conclusions of our paper - the Blossom paper mentions that Murtree outperforms Blossom for depth 5 or shallower; and we compare extensively with Murtree, with our primary paper results focusing on depth 5. \n\nIf you’d prefer to see a direct empirical comparison, we’re happy to look into that. Unfortunately, though we’ve made every attempt to do so, we haven't been able to run the approach by the end of the first rebuttal window - the codebase linked from the paper, https://gitlab.laas.fr/ehebrard/blossom , leads to a circular import error when we follow installation instructions on our machines (this looks to be a known issue that hasn’t yet been resolved - the latest commit to the repository adjusts the makefile/wrapper, and is titled “not quite”). Looking through the 9 works on google scholar that cite this work, none seem to have successfully run the approach and reported results, so we think this may be a larger issue than just our own environment. We're making our best effort to get an empirical comparison done in time. \n\n> Lookahead for policy improvement is a well-known technique in approximate dynamic programming and reinforcement learning. Maybe the authors should discuss the connection of this work to the DP and RL literature.\n\nLookahead for policy improvement is not quite the same as what we’re doing, though we agree discussion of these approaches in our related work would be warranted. We’re finding a globally optimal tree when behaviour is fixed to be greedy past a specific frontier, then postprocessing to improve behaviour past that frontier, with fixed behaviour beforehand. There is certainly a similar spirit of exploration and exploitation tradeoffs in our method, which we’re happy to discuss in related work.", "claims_and_evidence": "The central claim is that SPLIT achieves a sweet spot between greedy and optimal methods, providing near-optimal trees with significantly improved scalability. The experimental results in the paper seem to support this claim, showing substantial speedups compared to optimal methods with minimal loss in accuracy.", "methods_and_evaluation_criteria": "The proposed SPLIT algorithm and its variants (LicketySPLIT and RESPLIT) are clearly described. The evaluation criteria include accuracy, sparsity (number of leaves), and runtime, which are appropriate for the problem. The experiments are conducted on standard datasets, and the results are compared against greedy and optimal decision tree methods.", "theoretical_claims": "The authors theoretically prove that their algorithms scale exponentially faster in the number of features than optimal decision tree methods and can perform arbitrarily better than a purely greedy approach. I did not check the correctness of these proofs.", "experimental_designs_or_analyses": "The experimental design appears sound overall, comparing SPLIT against greedy (CART) and optimal decision tree algorithms.", "relation_to_broader_scientific_literature": "The paper effectively positions its contributions within the context of existing decision tree optimization methods. It clearly discusses the limitations of greedy and optimal approaches and how SPLIT aims to address them. The authors also relate their work to the concept of the Rashomon set in interpretable machine learning.", "essential_references_not_discussed": "The \"Blossom: An Anytime Algorithm for Computing Optimal Decision Trees\" paper by Demirović et al. (2023) is a relevant work that is not cited or discussed in the submission. Both papers address the challenge of finding optimal decision trees, with a focus on improving scalability and finite-time performance. Demirović et al. (2023) propose an anytime algorithm (Blossom) based on dynamic programming, which shares similarities with the SPLIT approach in terms of aiming for efficiency and anytime behavior. A comparison with Blossom would have strengthened the paper.", "other_strengths_and_weaknesses": "Strengths:\n* The proposed SPLIT algorithm is novel and offers a good balance between accuracy and scalability.   \n* The paper is well-written and the experimental results are convincing.\n* Recent developments in decision tree learning are thoroughly reviewed.", "other_comments_or_suggestions": "- It would be beneficial to discuss the limitations of the SPLIT algorithm in more detail, such as scenarios where it might underperform or when the greedy approximation is less effective.", "questions_for_authors": "Lookahead for policy improvement is a well-known technique in approximate dynamic programming and reinforcement learning. Maybe the authors should discuss the connection of this work to the DP and RL literature.", "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": "", "extra_scores": {}}, {"review_id": "d8ETk0lOMQ", "reviewer": "Reviewer_njLA", "summary": "The paper proposes three algorithms, SPLIT, LicketySPLIT, and RESPLIT, building from a common underlying technique to train near-optimal decision trees efficiently.\n\nOn one end of the decision tree training spectrum stands greedy algorithms, which are extremely fast but might create sub-optimal decision trees. On the other end stand methods like branch and bound, which can search for globally optimal splits and thus create optimal decision trees, but are extremely expensive computationally. The paper finds a compromise between the two methods, thus creating near-optimal decision trees almost as fast as the greedy algorithm.\n\nTheir technique is based on one critical insight, i.e., nodes near leaves can be split greedily without sacrificing significant performance. Thus, instead of performing the complete branch and bound training, the paper suggests doing optimal search only till some 'lookahead depth', and then splitting the rest of the tree greedily. This algorithm, which is called SPLIT, is able to achieve a large drop in training time while maintaining close to optimal performance.\n\nThe paper also proposed two other versions of this technique, called LicketySPLIT, to further improve the runtime, and RESPLIT, focused on finding the set of near-optimal models (i.e., the Rashomon set). Their method is compared against several SOTA techniques, showing consistently good performance and faster training, thus empirically verifying the claims.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! We really appreciate your feedback on the organization - since ICML allows an additional page for accepted submissions, we’d be happy to move some of the intuition for greedy splits near the leaves, as well as a discussion of RESPLIT and the Rashomon Set, from the appendix into the main paper. It is really helpful to know that you found that to be important enough to include in the main paper.", "claims_and_evidence": "Claims made in the paper about the runtime of their algorithms are well supported by both theoretical proofs and empirical results.\n\nClaims made in the paper about the performance benefits of their algorithms in real-world datasets are well supported by empirical results. There are also some theoretical results to support performance benefits, however these results aren't too strong in my opinion. But then again, the paper never promises any such strong theoretical proofs, so no complaints really.", "methods_and_evaluation_criteria": "The paper promises a new algorithm to train faster yet near-optimal decision trees. All techniques are compared on two axes: training time and performance, and thus the comparisons make sense for the application at hand. The paper uses a diverse set of datasets for evaluation, with many more present in the Appendix. Overall, the evaluation setup makes sense to me.", "theoretical_claims": "I checked the correctness of proofs for Theorem 5.4 (runtime for LicketySPLIT) and Theorem 5.5 (performance guarantees against greedy method). I believe they are both correct. There were many other theorems for the runtime of other versions of the algorithm (such as SPLIT or RESPLIT), however, I did not check the correctness of these claims in detail.", "experimental_designs_or_analyses": "The details of the experimental design are present in the paper, and I believe can be reproduced with some effort.\n\nThe experimental analysis seemed valid to me. I did not spot any issues.", "relation_to_broader_scientific_literature": "Decision trees are a vital part of interpretable ML research. By providing an algorithm to train decision trees significantly faster than any existing technique, while still maintaining near-optimal performance, this work can impact both (a) future work in interpretable ML, and (b) real-world training and deployment of ML models.", "essential_references_not_discussed": "I'm not too familiar with related work in the field. However, I enjoyed reading the related work section of the paper, and I don't believe there were any missing references in the paper.", "other_strengths_and_weaknesses": "The paper is very well written and I thoroughly enjoyed reading it.\n\nI do wish there were certain changes to the organization of the paper, however, I understand the choices made given the limited space. Hence, it is not really a weakness of the paper, but simply some suggestions that I wished to see in the paper (and are thus, listed in the next section).", "other_comments_or_suggestions": "1. There should be some intuition or support for why splitting the trees greedily near the leaves works well. The empirical results of Appendix A.2 and A.3 are quite nice, but without their presence in the main text, the algorithm SPLIT almost feels like something the paper 'stumbled' into. Throughout the main paper, I never got an answer to 'why' the paper decided to split the trees near the leaves greedily. A suggestion: Maybe a compressed version of the discussion in Appendix A.2 and Figure 7 can find a home somewhere in the main paper?\n2. I wish there was a better discussion of RESPLIT and the Rashomon sets in the main paper. Again, yes, some results are present in the Appendix, but in my opinion, the creation of the Rashomon set is an extremely important application of the SPLIT algorithm, as the cost of training multiple models would explode with other complex training techniques currently present in the literature.\n\nA purely personal take on the organization of the paper: While I really enjoyed reading the related work and preliminary sections, I believe a lot of those discussions didn't necessarily need to be in the main paper. Similarly, the theorems and theoretical results too didn't need to be in the main paper. Instead, I think the paper can have a wider appeal if the space in the main paper is given to the two things mentioned above.\n\nHowever, the authors might disagree, and I won't hold that against the paper at all. It was an overall delightful read.", "questions_for_authors": "NA", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper introduces methods for finding decision trees that enjoys high accuracy and scalability often found in greedy algorithms. The proposed algorithms are tested against benchmarks and to characterize the Rashomon Set of decision trees.

Overall, this is an excellent paper that significantly moves the needle in finding models that are accurate and interpretable. The reviewers were unanimous in accepting the paper. Decision trees are widely used in a variety of applications, can be very accurate, and are interpretable. This paper makes an important contribution to this area.

I encourage the authors to take the reviewers' comments into account when polishing their camera-ready version.
Decision: Accept (oral)