{'fraction_non_alphanumeric': 0.039105079572705474, 'fraction_numerical': 0.012576302594288206, 'mean_word_length': 4.371660689453268, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 3, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Fast Sparse Decision Tree Optimization via Reference Ensembles

Sparse decision tree optimization has been one of the most fundamental problems in AI since its inception and is a challenge at the core of interpretable machine learning. Sparse decision tree optimization is computationally hard, and despite steady effort since the 1960's, breakthroughs have only been made on the problem within the past few years, primarily on the problem of finding optimal sparse decision trees. However, current state-of-the-art algorithms often require impractical amounts of computation time and memory to find optimal or near-optimal trees for some real-world datasets, particularly those having several continuous-valued features. Given that the search spaces of these decision tree optimization problems are massive, can we practically hope to find a sparse decision tree that competes in accuracy with a black box machine learning model? We address this problem via smart guessing strategies that can be applied to any optimal branch-and-bound-based decision tree algorithm. We show that by using these guesses, we can reduce the run time by multiple orders of magnitude, while providing bounds on how far the resulting trees can deviate from the black box's accuracy and expressive power. Our approach enables guesses about how to bin continuous features, the size of the tree, and lower bounds on the error for the optimal decision tree. Our experiments show that in many cases we can rapidly construct sparse decision trees that match the accuracy of black box models. To summarize: when you are having trouble optimizing, just guess.


Introduction
Decision trees are one of the leading forms of interpretable AI models. Since the development of the first decision tree algorithm (Morgan and Sonquist 1963), a huge number of algorithms have been proposed to improve both accuracy and run time. However, major approaches are based on decision tree induction, using heuristic splitting and pruning (e.g., Breiman et al. 1984;Quinlan 1993). Growing a tree in a greedy way, though fast, leads to suboptimal models with no indication of how far away the solution is from optimality. The generated trees are usually much more complicated than they need to be, hindering interpretability. Optimizing sparse decision trees remains one of the most fundamental problems in machine learning (ML).
Full decision tree optimization is NP-hard (Laurent and Rivest 1976), leading to challenges in searching for optimal trees in a reasonable time, even for small datasets. Major advances have been made recently using either mathematical programming solvers (e.g., Verwer and Zhang 2019) or customized branch-and-bound with dynamic programming (Aglin, Nijssen, and Schaus 2020;Lin et al. 2020;Demirović et al. 2020), showing us that there is hope. However, these methods are frequently unable to find the optimal tree within a reasonable amount of time, or even if they do find the optimal solution, it can take a long time to prove that the tree is optimal or close-to-optimal.
Ideally, we would like an algorithm that, within a few minutes, produces a sparse decision tree that is as accurate as a black box machine learning model. Also, we wish to have a guarantee that the model will have performance close to that of the black box. We present a practical way to achieve this by introducing a set of smart guessing techniques that speed up sparse decision tree computations for branch-and-bound methods by orders of magnitude.
The key is to guess in a way that prunes the search space without eliminating optimal and near-optimal solutions. We derive those smart guesses from a black box tree-ensemble reference model whose performance we aim to match. Our guesses come in three flavors. The first type of guess reduces the number of thresholds we consider as a possible split on a continuous feature. Here, we use splits generated by black box ensembles. The second type of guess concerns the maximum depth we might need for an optimal tree, where we relate the complexity of a tree ensemble to the depth of an equivalently complex class of individual trees. The third type of guess uses the accuracy of black box models on subsets of the data to guess lower bounds on the loss for each subproblem we encounter. Our guesses are guaranteed to predict as well or better than the black box tree-ensemble reference model: taking the sparsest decision tree that makes the same predictions as the black box, our method will find this tree, an equivalently good tree, or an even better one. Together, these guesses decrease the run time by several orders of magnitude, allowing fast production of sparse and interpretable trees that achieve black box predictive performance. arXiv:2112.00798v7 [cs.LG] 6 Jul 2022 2 Related Work Our work relates to the field of decision tree optimization and thinning tree ensembles.
Decision tree optimization. Optimization techniques have been used for decision trees from the 1990s until the present (Bennett and Blue 1996;Dobkin et al. 1997;Farhangfar, Greiner, and Zinkevich 2008;Nijssen andFromont 2007, 2010). Recently, many works have directly optimized a performance metric (e.g., accuracy) with soft or hard sparsity constraints on the tree size. Such decision tree optimization problems can be formulated using mixed integer programming (MIP) (Bertsimas and Dunn 2017;Verwer and Zhang 2019;Vilas Boas et al. 2021;Günlük et al. 2021;Rudin and Ertekin 2018;Aghaei, Gómez, and Vayanos 2021). Other approaches use SAT solvers to find optimal decision trees (Narodytska et al. 2018;Hu et al. 2020), though these techniques require data to be perfectly separable, which is not typical for machine learning. Carrizosa, Molero-Río, and Morales (2021) provide an overview of mathematical programming for decision trees.
Another branch of decision tree optimization has produced customized dynamic programming algorithms that incorporate branch-and-bound techniques. Hu, Rudin, and Seltzer (2019); Angelino et al. (2018); Chen and Rudin (2018) use analytical bounds combined with bit-vector based computation to efficiently reduce the search space and construct optimal sparse decision trees. Lin et al. (2020) extend this work to use dynamic programming. Aglin, Nijssen, and Schaus (2020) also use dynamic programming with bounds to find optimal trees of a given depth. Demirović et al. (2020) additionally introduce constraints on both depth and number of nodes to improve the scalability of decision tree optimization.
Our guessing strategies can further improve the scalability of all branch-and-bound based optimal decision tree algorithms without fundamentally changing their respective search strategies. Instead, we reduce time and memory costs by using a subset of thresholds and tighter lower bounds to prune the search space.
"Born-again" trees. Breiman and Shang (1996) proposed to replace a tree ensemble with a newly constructed single tree. The tree ensemble is used to generate additional observations that are then used to find the best split for a tree node in the new tree. Zhou and Hooker (2016) later follow a similar strategy. Other recent work uses black box models to determine splitting and stopping criteria for growing a single tree inductively (Bai et al. 2019) or exploit the class distributions predicted by an ensemble to determine splitting and stopping criteria (Van Assche and Blockeel 2007). Vandewiele et al. (2016) use a genetic approach to construct a large ensemble and combine models from different subsets of this ensemble to get a single model with high accuracy.
Another branch of work focuses on the inner structure of the tree ensemble. Akiba, Kaneda, and Almuallim (1998) generate if-then rules from each of the ensemble classifiers and convert the rules into binary vectors. These vectors are then used as training data for learning a new decision tree. Recent work following this line of reasoning extracts, ranks, and prunes conjunctions from the tree ensemble and organizes the set of conjunctions into a rule set (Sirikulviriya and Sinthupinyo 2011), an ordered rule list (Deng 2019), or a single tree (Sagi and Rokach 2020). Hara and Hayashi (2018) adopt a probabilistic model representation of a tree ensemble and use Bayesian model selection for tree pruning.
The work of Vidal and Schiffer (2020) produces a decision tree of minimal complexity that makes identical predictions to the reference model (a tree ensemble). Such a decision tree is called a born-again tree ensemble.
We use a reference model for two purposes: to help reduce the number of possible values one could split on and to determine an accuracy goal for a subset of points. By using a tree ensemble as our reference model, we can guarantee that our solution will have a regularized objective that matches or improves upon that of any born-again tree ensemble.

Notation and Objectives
We denote the training dataset as {(x i , y i )} N i=1 , where x i are M -vectors of features, and y i ∈ {0, 1} are labels. Let x be the N × M covariate matrix and y be the N -vector of labels, and let x ij denote the j-th feature of x i . We transform each continuous feature into binary features by creating a split point at the mean value between every ordered pair of unique values present in the training data. Let k j be the number of unique values realized by feature j, then the total number of features isM = M j=1 (k j − 1). We denote the binarized covariate matrix asx wherex i ∈ {0, 1}M are binary features.
Let L(t,x, y) = 1 be the loss of the tree t on the training dataset, given predictions {ŷ t i } N i=1 from tree t. Most optimal decision tree algorithms minimize a misclassification loss constrained by a depth bound, i.e., minimize t L(t,x, y), s.t. depth(t) ≤ d. (1) Instead, Hu, Rudin, and Seltzer (2019) and Lin et al. (2020) define the objective function R(t,x, y) as the combination of the misclassification loss and a sparsity penalty on the number of leaves. That is, R(t,x, y) = L(t,x, y) + λH t , where H t is the number of leaves in the tree t and λ is a regularization parameter. They minimize the objective function, i.e., minimize t L(t,x, y) + λH t .
Ideally, we prefer to solve (2) since we do not know the optimal depth in advance, and even at a given depth, we would prefer to minimize the number of leaves. But (1) is much easier to solve. We discuss details in Section 4.2.

Guessing Thresholds via Column Elimination
Since most state-of-the-art optimal decision tree algorithms require binary inputs, continuous features require preprocessing. We can transform a continuous feature into a set of binary dummy variables. Call each midpoint between two consecutive points a split point. Unfortunately, naïvely creating split points at the mean values between each ordered pair of unique values present in the training data can dramatically increase the search space of decision trees (Lin et al. 2020, Theorem H.1), leading to the possibility of encountering either a time or memory limit. Verwer and Zhang (2019) use a technique called bucketization to reduce the number of thresholds considered: instead of including split points between all realized values of each continuous feature, bucketization removes split points between realized feature values for which the labels are identical. This reduces computation, but for our purposes, it is still too conservative, and will lead to slow run times. Instead, we use a subset of thresholds from our reference boosted decision tree model, since we know that with these thresholds, it is possible to produce a model with the accuracy we are trying to match. Because computation of sparse trees has factorial time complexity, each feature we remove reduces run time substantially. Column Elimination Algorithm: Our algorithm works by iteratively pruning features (removing columns) of least importance until a predefined threshold is reached: 1) Starting with our reference model, extract all thresholds for all features used in all of the trees in the boosting model. 2) Order them by variable importance (we use Gini importance), and remove the least important threshold (among all thresholds and all features). 3) Re-fit the boosted tree with the remaining features. 4) Continue this procedure until the training performance of the remaining tree drops below a predefined threshold. (In our experiments, we stop the procedure when there is any drop in performance at all, but one could use a different threshold such as 1% if desired.) After this procedure, the remaining data matrix is denoted byx reduced T . If, during this procedure, we eliminate too many thresholds, we will not be able to match black box accuracy. Theorem 4.1 bounds the gap between the loss of the black-box tree ensemble and loss of the optimal tree after threshold guessing.
Let T be the ensemble tree built with (x reduced T , y). We consider t to be any decision tree that makes the same predictions as T for every observation inx reduced T . We provide Figure 8 in the appendix as an illustration of finding a t with the minimum number of leaves for a given ensemble. Note that H t may be relatively small even if T is a fairly large ensemble, because the predictions are binary (each leaf predicts either 0 or 1) and the outcomes tend to vary smoothly as continuous features change, with not many jumps. Theorem 4.1. (Guarantee for model on reduced data). Define the following: • Let T be the ensemble tree built upon (x, y).
• Let T be the ensemble tree built with (x reduced T , y).
• Let t be any decision tree that makes the same predictions as T for every observation inx reduced T . • Let t * ∈ arg min t L(t,x reduced T , y) + λH t be an optimal tree on the reduced dataset.
That is, for any tree t that matches the predictions of T forx reduced T (even the smallest such tree), the difference in loss between the black box tree ensemble T and the optimal single tree t * (based onx reduced T ) is not worse than the regularization coefficient times the difference between the sizes of two trees: t * and t . Equivalently, t * will never be worse than t in terms of the regularized objective. If we pick t to be a born-again tree ensemble for T (Vidal and Schiffer 2020) (which we can do because born-again tree ensembles make the same predictions as T for all inputs, and therefore make the same predictions forx reduced T ), we can show that our thresholding approach guarantees that we will never do worse than the best born-again tree ensemble for our simplified reference model, in terms of the regularized objective. If we pick a t with the minimal number of leaves, this theorem shows we even match or beat the simplest tree that can exactly replicate the reference models' predictions on the training set.

Guessing Depth
As discussed in Section 3, there are two different approaches to producing optimal decision trees: one uses a hard depth constraint and the other uses a per-leaf penalty. Algorithms that use only depth constraints tend to run more quickly but can produce needlessly complicated trees, because they do not reward trees for being shallower than the maximum depth. Depth constraints assess trees only by the length of their longest path, not by any other measure of simplicity, such as the length of the average path or the number of different decision paths. In contrast, per-leaf penalty algorithms (Hu, Rudin, and Seltzer 2019; Lin et al. 2020) produce sparse models, but frequently have longer running times, as they search a much larger space, because they do not assume they know the depth of an optimal tree. We show that by adding a depth constraint (a guess on the maximum depth of an optimal tree) to per-leaf penalty algorithms, such as GOSDT (Lin et al. 2020), we can achieve per-leaf sparsity regularization at run times comparable to depth-constrained algorithms, such as DL8.5 (Aglin, Nijssen, and Schaus 2020). In particular, we combine (1) and (2) to produce a new objective, where we aim to choose d such that it reduces the search space without removing all optimal or near-optimal solutions. Most papers use depth guesses between 2 and 5 (Aglin, Nijssen, and Schaus 2020), which we have done in our experiments. However, Theorem 4.2 provides guidance on other ways to select a depth constraint to train accurate models quickly. Also, Theorem A.1 bounds the gap between the objectives of optimal trees with a relatively smaller depth guess and with no depth guess. This gap depends on the trade-off between sparsity and accuracy.
Interestingly, using a large depth constraint is often less efficient than removing the depth constraint entirely for GOSDT, because when we use a branch-and-bound approach with recursion, the ability to re-use solutions of recurring subproblems diminishes in the presence of a depth constraint.
Theorem 4.2. (Min depth needed to match complexity of ensemble). Let B be the base hypothesis class (e.g., decision stumps or shallow trees) that has VC dimension at least 3 and let K ≥ 3 be the number of weak classifiers (members of B) combined in an ensemble model. Let F ensemble be the set of weighted sums of weak classifiers, i.e., T ∈ F ensemble has T (x) = sign( Let F d,tree be the class of single binary decision trees with depth at most: It is then true that VC(F d,tree ) ≥ VC(F ensemble ).
That is, the class of single trees with depth at most d has complexity at least that of the ensemble. The following results are special cases of Theorem 4.2: • Suppose B is the class of decision trees with depth at most 3. To match or exceed the complexity of an ensemble of K = 10 trees from B with a single tree, it is sufficient to use trees of depth 11. • Suppose B is the class of decision trees with depth at most 3. To match or exceed the complexity of an ensemble of K = 100 trees from B with a single tree, it is sufficient to use trees of depth 15. The bound is conservative, so we might choose a smaller depth than is calculated in the theorem; the theorem provides an upper bound on the depth we need to consider for matching the accuracy of the black box.

Guessing Tighter Lower Bounds
Branch-and-bound approaches to decision tree optimization, such as GOSDT and DL8.5, are limited by the inefficiency of their lower bound estimates. To remove a potential feature split from the search, the algorithm must prove that the best possible (lowest) objectives on the two resulting subproblems sum to a value that is worse (larger) than optimal. Calculating tight enough bounds to do this is often slow, requiring an algorithm to waste substantial time exploring suboptimal parts of the search space before it can prove the absence of an optimal solution in that space.
We use informed guesses to quickly tighten lower bounds. These guesses are based on a reference model -another classifier that we believe will misclassify a similar set of training points to an optimal tree. Let T be such a reference model andŷ T i be the predictions of that reference model on training observation i. Define s a as the subset of training observations that satisfy a boolean assertion a: We can then define our guessed lower bound as the disagreement of the reference and true labels for these observations (plus a penalty reflecting that at least 1 leaf will be used in solving this subproblem): We use this lower bound to prune the search space. In particular, we consider a subproblem to be solved if we find a subtree that achieves an objective less than or equal to its lb guess (even if we have not proved it is optimal); this is equivalent to assuming the subproblem is solved when we match the reference model's accuracy on that subproblem. We further let the algorithm omit any part of the space whose estimated lower bound is large enough to suggest that it does not contain an optimal solution. That is, for each subproblem, we use the reference model's accuracy as a guide for the best accuracy we hope to obtain. Thus, we introduce modifications to a general branch-andbound decision tree algorithm that allow it to use lower bound guessing informed by a reference model. We focus here on approaches to solve (3), noting that (1) and (2) are special cases of (3). For a subset of observations s a , let t a be the subtree used to classify those points, and let H ta be the number of leaves in that subtree. We can then define: R(t a ,x(s a ), y(s a )) = 1 N i∈sa 1[y i =ŷ ta i ] + λH ta . For any dataset partition A, where a ∈ A corresponds to the data handled by a given subtree of t: Given a set of observations s a and a depth constraint d for which we want to find an optimal tree, consider the partition of s a resulting from "splitting" on a given boolean feature j inx, i.e., the sets given by: Let t * a∩j,d−1 be the optimal solution to the set of observations s a ∩ s j with depth constraint d − 1, and let t * a∩j c ,d−1 be similarly defined for the set of observations s a ∩ s c j . To find the optimal tree given the indices s a and the depth constraint d, one approach is to find the first split by solving minimize j R(t * a∩j,d−1 ,x(s a ∩ s j ), y(s a ∩ s j )) This leads to recursive subproblems representing different sets of observations and depth constraints. One can solve for all splits recursively according to the above equation. Our modification to use lower bound guessing informed by a reference model applies to all branch-and-bound optimization techniques that have this structure. Define majority(s a ) as the majority label class in s a , and let ub(s a ) be the objective of a single leaf predicting majority(s a ) for each point in s a : ub(s a ) = 1 N i∈sa 1[y i = majority(s a )] + λ, where (as usual) λ is a fixed per-leaf penalty for the model. A recursive branch-and-bound algorithm using lower bound guessing finds a solution for observations s a with depth constraint d with the following modifications to its ordinary approach (see Appendix G for further details). Note that the subproblem is identified by (s a , d).
Lower-bound Guessing for Branch-and-Bound Search 1. (Use guess to initialize lower bound.) If ub(s a ) ≤ lb guess (s a )+λ or d = 0, we are done with the subproblem. We consider it solved with objective ub(s a ), corresponding to a single leaf predicting majority(s a ). Otherwise, set the current lower bound lb curr (s a , d) = lb guess (s a ) and go to Step 2. 2. Search the space of possible trees for subproblem (s a , d) by exploring the possible features on which the subproblem could be split to form two new subproblems, with depth constraint d − 1, and solving those recursively. While searching: (a) (Additional termination condition if we match black box performance.) If we find a subtree t for subproblem (s a , d) with R(t,x(s a ), y(s a )) ≤ lb current (s a , d), we are done with the subproblem. We consider it solved with objective R(t,x(s a ), y(s a )), corresponding to subtree t. (b) (Modified lower bound update.) At any time, we can opt to update the lower bound for the subproblem (with d as shorthand for d − 1): (This corresponds to splitting on the best feature.) lb curr (s a , d) ← max(lb curr (s a , d), min(ub(s a ), lb spl )) (Here, min(ub(s a ), lb spl ) is the better of not splitting on any feature and splitting on the best feature. The max ensures that our lower bounds never decrease. The lb curr term comes from either our initial lower bound guess or the lower bound we have so far.) If the lower bound increases to match ub(s a ), we are done with the subproblem. We consider it solved with objective ub(s a ), corresponding to a single leaf predicting majority(s a ). If the lower bound increases but does not match ub(s a ), we apply Case 2a with the new, increased lb curr (s a , d).
This approach is provably close to optimal when the reference model makes errors similar to an optimal tree. Let s T,incorrect be the set of observations incorrectly classified by the reference model T , i.e., s T,incorrect = {i|y i =ŷ T i }. Let t guess be a tree returned from our lower-bound guessing algorithm. The following theorem holds: Theorem 4.3. (Guarantee on guessed model performance). Let R(t guess ,x, y) denote the objective of t guess on the full binarized dataset (x, y) for some per-leaf penalty λ (and with t guess subject to depth constraint d). Then for any decision tree t that satisfies the same depth constraint d, we have: That is, the objective of the guessing model is no worse than the union of errors made by the reference model and tree t.
The most significant consequence of this theorem is that R(t guess ,x, y) − R(t * ,x, y) where we selected t * , an optimal tree for the given λ and depth constraint, as t, and we subtracted R(t * ,x, y) from both sides. This means that if the data points misclassified by the black box are a subset of the data points misclassified by the optimal decision tree, we are guaranteed not to lose any optimality. However much optimality we lose is a function of how many data points misclassified by the black box could have been correctly classified by the optimal tree. We also prove that adding lower bound guessing after using threshold guessing does not change the worst case performance from Theorem 4.1. Corollary 4.3.1. Let T , T and t be defined as in Theorem 4.1. Let t guess be the tree obtained using lower-bound guessing with T as the reference model, onx reduced T , y, with depth constraint matching or exceeding the depth of t . Then L(t guess ,x reduced T , y)−L(T, x, y) ≤ λ(H t −H tguess ), or equivalently, R(t guess ,x reduced T , y) ≤ L(T, x, y) + λH t . The difference between this corollary and Theorem 4.1 is that it uses t guess rather than t * , without any weakening of the bound. Because of this corollary, our experimental results focus on lower bound guessing in combination with threshold guessing, using the same reference model, rather than using lower bound guessing on its own.

Experiments
Our evaluation addresses the following questions: Unless stated otherwise, all plots show the median value across 5 folds with error bars corresponding to the first and third quartile. We use GBDT as the reference model for guessing and run it using scikit-learn (Pedregosa et al. 2011). We configure GBDT with default parameters, but select datasetspecific values for the depth and number of weak classifiers: (n_est, max_depth) = (20, 3) for COMPAS and Spiral, (40, 1) for Broward and FICO, (50, 2) for Takeaway and Restaurant, and (30, 2) for Netherlands. Appendix C presents details about our hyper-parameter selection process, and Appendix B presents the experimental setup and more details about the datasets.

Performance With and Without Guessing
Our first experiments support our claim that using guessing strategies enables optimal decision tree algorithms to quickly find sparse trees whose accuracy is competitive with a GBDT that was trained using 100 max-depth 3 weak classifiers. Figure 1 shows training and testing results on the COM-PAS data set. (Results for the other data sets are in Appendix C.1.) The difference between the stars and the circles shows that our guessing strategies dramatically improve both DL8.5 and GOSDT run times, typically by 1-2 orders of magnitude. Furthermore, the trees we created have test accuracy that sometimes beats the black box, because the sparsity of our trees acts as regularization. Figure 2 shows the accuracy-sparsity tradeoff for different decision tree models (with GBDT accuracy indicated by the black line). The batree results are for the Born-Again tree ensembles of Vidal and Schiffer (2020). Results for the remaining datasets (which are similar) appear in Appendix C.2. The guessed models are both sparse and accurate, especially with respect to CART and batree.
We also compare GOSDT with all three guessing strategies to Interpretable AI's Optimal Decision Trees package, a proprietary commercial adaptation of Optimal Classification Tree (OCT) (Bertsimas and Dunn 2017) in Appendix H. The results show the run time of the two methods is comparable despite the fact that GOSDT provides guarantees on accuracy while the adaptation of OCT does not. GOSDT with all three guesses tends to find sparser trees with comparable accuracy.

Efficacy of Different Guessing Techniques
Comparing the three graphs in Figure 1 shows how guessing different depths affects run time performance. For the next three experiments, we fix the maximum depth to 5 and examine the impact of the other guessing strategies.
Guessing Thresholds: We found that guessing thresholds has the most dramatic impact, so we quantify that impact first. We compare the training time and accuracy with and without threshold guessing for GOSDT and DL8.5 on seven datasets. We limit run time to 30 minutes and run on a machine with 125GB memory. Experiments that time out are shown with orange bars with hatches; Experiments that run out of memory are in gray with hatches. If the experiment timed out, we analyze the best model found at the time of the timeout; if we run out of memory, we are unable to obtain a model. Figure  3 shows that the training time after guessing thresholds (blue bars) is orders of magnitude faster than without thresholds guessing (orange bars). Orange bars are bounded by the time limit (1800 seconds) set for the experiments, but in reality, the training time is much longer. Moreover, threshold guessing leads to little change in both training and test accuracy dl8.5+th+lb Ours gosdt+th+lb gosdt (no depth limit)+th+lb Baselines cart batree GBDT Figure 2: (Sparsity vs. Accuracy). DL8.5 and GOSDT use guessed thresholds and guessed lower bounds. CART is trained on the original dataset with no guess. This figure shows that our guessed trees define a frontier; we achieve the highest accuracy for almost every level of sparsity. The baseline methods (CART, batree) do not achieve results on the frontier. gosdt/dl8.5 timeout reference model training time Ours gosdt/dl8.5 memory out gosdt+th/dl8.5+th training time Baselines Figure 3: (Value of Threshold Guessing). Training time (logscale) for GOSDT and DL8.5 with depth limit 5. All baselines (hatched) timed out (orange) or hit the memory limit (gray). Green parts indicate threshold guessing times.
Guessing Lower Bounds: Next, we add lower-bound guesses to the threshold guesses to produce Figure 4. The results are qualitatively similar to those in Figure 3: using lower bound guesses produces an additional run time benefit. Appendix C.4 shows more results and verifies that using lower-bound guesses often leads to a solution with the same training error as without lower-bound guesses or leads to finding a simpler solution with test error that is still comparable to the solution found without lower-bound guessing.
Value of Depth Constraints: We examine depth constraints' effect on GOSDT in Figure 5. We run GOSDT without a depth constraint, which produces an optimal tree for each of five folds using per-leaf regularization, and compare to GOSDT with a depth constraint. Above a certain threshold, depth constraints do not reduce training accuracy (since the constraint does not remove all optimal trees from the search space). Some depth constraints slightly improve test accu- racy (see depths 4 and 5), since constraining GOSDT to find shallower trees can prevent or reduce overfitting. Usually, depth constraints allow GOSDT to run several orders of magnitude faster. For large depth constraints, however, the run time can be worse than that with no constraints. Using depth guesses reduces GOSDT's ability to share information between subproblems. When the constraint prunes enough of the search space, the search space reduction dominates; if the constraint does not prune enough, the inability to share subproblems dominates.

When Guesses Are Wrong
Although rare in our experiments, it is possible to lose accuracy if the reference model is too simple, i.e., only a few thresholds are in the reduced dataset or too many samples are misclassified by the reference model. This happens when we choose a reference model that has low accuracy to begin with. Thus, we should check the reference model's performance before using it and improve it before use if necessary. Appendix D shows that if one uses a poor reference model, we do lose performance. Appendix C shows that for a wide range of reasonable configurations, we do not suffer dramatic performance costs as a result of guessing.

Trees
We qualitatively compare trees produced with our guessing technique to several baselines in Figure 6. We observe that with all three guessing techniques, the resulting trees are not only more accurate overall, but they are also sparser than the trees produced by the baselines. Figure 7 shows example GOSDT trees trained using all three guesses on the COMPAS dataset. Appendix C.5 shows more output trees and Appendix F compares decision sets transformed from our trees and trained by Dash, Gunluk, and Wei (2018) on the FICO dataset.
Ours Baselines timeout timeout Figure 6: (Tree Visualization). Trees for GOSDT and DL8.5. Dots indicate the data points and the shaded areas are the corresponding classification by the tree. GOSDT trees were trained with and without all three guesses (d = ∞ means no depth constraint). DL8.5 trees were trained with and without threshold and lower bound guesses at depth 5. CART was trained with depth 5 and batree was trained using random forests with 10 max-depth 3 weak classifiers as the reference model. Training time is 1.606 seconds for GOSDT with all three guesses and 0.430 seconds for DL8.5 with all three guesses (left column). Both GOSDT without guesses and DL8.5 with only depth guesses timed out (middle column).

Conclusion
We introduce smart guessing strategies to find sparse decision trees that compete in accuracy with a black box machine learning model while reducing training time by orders of magnitude relative to training a fully optimized tree. Our guessing strategies can be applied to several existing optimal decision tree algorithms with only minor modifications. With these guessing strategies, powerful decision tree algorithms can be used on much larger datasets.

A Theorems and Proofs
A.1 Proof of Theorem 4.1 Theorem 4.1 (Guarantee for model on reduced data). Define the following: • Let T be the ensemble tree built upon (x, y).
• Let T be the ensemble tree built with (x reduced T , y).
• Let t be any decision tree that makes the same predictions as T for every observation inx reduced T .
• Let t * ∈ arg min t L(t,x reduced T , y) + λH t be an optimal tree on the reduced dataset.
Proof. When we are buildingx reduced T (the dataset used to construct T ), the stopping condition of column elimination is that accuracy decreases, which is when the loss increases: L(T, x, y) < L(T ,x reduced T , y). Thus, the opposite must always be true as we build T : L(T ,x reduced T , y) ≤ L(T, x, y). Since H t is the number of leaves in the single tree that exactly replicates the predictions of T and since t * is an optimal tree, A.2 Proof of Theorem 4.2 Theorem 4.2 Let B be the base hypothesis class (e.g., decision stumps) that has VC dimension at least 3 and K ≥ 3 be the number of weak classifiers. Let F ensemble be the set of models that are a weighted sum of shallow trees for classification, i.e., Let F d,tree be the class of single binary decision trees with depth at most: d = log 2 ((K · VC(B) + K) · (3 ln(K · VC(B) + K) + 2)) .
It is then true that VC(F d,tree ) ≥ VC(F ensemble ).
Proof. Since K and V C(B) are both greater than or equal to 3 and since T ∈ F ensemble has T (x) = sign( K k=1 w k h k (x)), where ∀k, w k ∈ R, h k ∈ B, then according to Shalev-Shwartz and Ben-David (2014, Lemma 10.3), Since F d, tree is the class of single binary decision trees with depth at most d, 2 d samples can be shattered by trees in F d, tree . That is, setting d to the value in the statement of the theorem, V C(F d, tree ) = 2 log 2 ((K·VC(B)+K)·(3 ln(K·VC(B)+K)+2)) .
A.3 Bound for the gap between the objectives of optimal trees with a relatively smaller depth guess and with no depth guess Theorem 4.2 gives an upper bound of depth guess we can make to compete with a boosted tree. However, it is often too loose to be an effective guess. Ideally, we want to guess depth that matches the true depth, but it is likely that our guess is small. Theorem A.1 bounds the gap between the objectives of optimal trees with a relatively smaller depth guess and with no depth guess. We first introduce some notation. Let Ω be a set of leaves. Capture is an indicator function that equals 1 ifx i falls into one of the leaves in Ω, and 0 otherwise, in which case we say that cap( we define a set of observations to be equivalent if they have exactly the same feature values, i.e.,x i =x j when i = j. Note that a dataset contains multiple sets of equivalent points (i.e., equivalence classes), denoted by {e u } U u=1 . Each observation belongs to an equivalence class e u (which has 1 element if the observation is unique). We denote q u as the minority label class among observations in e u . In this case, the number of observations with the minority label in set e u is Theorem A.1. Let t * be an optimal decision tree, i.e. t * ∈ arg min t L(t,x, y) + λH t and d * be the depth of t * . Define d guess as a guessed depth and assume that d guess < d * (that is, the guessed depth is too small). Now, let t * guess ∈ arg min t L(t,x, y) + λH t s.t. depth(t) ≤ d guess (which is the best tree we could create with the guessed depth). Let t guess be the tree obtained by pruning all leaves below d guess in t * and let (l 1 , ..., l H t guess ) be leaves of t guess . Then, Figure 9: An example demonstrating t * guess , t * , and t guess in Theorem A.1. Figure 9 shows an example of trees in Theorem A.1. Suppose the true depth of the optimal tree t * is 3 (subfigure b) and d guess is 2. In this toy example, we can remove the leaf pair at depth 3 in t * to get t guess (subfigure c). And t * guess shown in subfigure (a) is an optimal tree given depth constraint which can have different internal nodes compared with t guess .
Proof. Since t * is the optimal tree with no depth guess and t * guess is the optimal tree with depth guess where d guess is assumed to be smaller than d * , R(t * ,x, y) ≤ R(t * guess ,x, y). Since t guess is a tree obtained by pruning all leaves below d guess in t * , Moreover, since the loss of the optimal tree is always no less than the number of equivalent points over the sample size, i.e. # of equivalent points N , According to Theorem A.1, although it is possible to have a penalty to the objective when picking a depth constraint that is too small (because we no longer consider the optimal tree), this penalty is somewhat offset by the reduced complexity of the models in the new search space.
A.4 Proof of Theorem 4.3 Theorem 4.3 Let R(t guess ,x, y) denote the objective of t guess on the full binarized dataset (x, y) for some per-leaf penalty λ (and with t guess subject to some depth constraint d). Then for any decision tree t that satisfies the same depth constraint d, we have That is, the objective of the guessing model is no worse than the union of errors made by the reference model and tree t.
For this proof, we use the following notation to discuss lower bounds: • λ ≥ 0 is a regularizing term (a per-leaf penalty added to the risk function when evaluating each tree) • For some decision tree t, we calculate its risk as R(t,x, y) = 1 where H t refers to the number of leaves in tree t.
• T is a reference model we use to guess lower bounds. • s T,correct and s T,incorrect are, respectively, the indices of the set of observations in the training set correctly classified by T and the set of observations incorrectly classified by T . • s a is the set of training set observations captured in our current subproblem. • d represents the maximum allowed depth for solutions to our current subproblem. If d = 0, no further splits are allowed. • t guess (s a , d, λ) is the lower-bound-guessing-algorithm's solution for subproblem s a , depth limit d, and regularizer λ. When we just specify t guess without arguments, we are referring to the lower-bound-guessing-algorithm's solution for the root subproblem (the whole dataset), with the depth limit argument provided for the tree as a whole. • Consider a subproblem s a corresponding to the full set of points passing through a specific internal or leaf node of the optimal tree t * (call it node t * ,sa ). Define H t * a as the number of leaves below node sa (or 1 if node sa is a leaf). Note that this is also the number of leaves needed in an optimal solution for subproblem s a . Similarly define H tguess,a as the number of leaves below node tguess,sa in t guess (when s a corresponds to the full set of points passing through a node in t guess ). Note that this does not necessarily correspond to the number of leaves needed in an optimal solution for subproblem s a because t guess has not been fully optimized. • R guess (s a , d, λ) is the objective of the solution found for subproblem s a , depth limit d, and regularizer λ when we use lower bound guessing: • lb guess (s a ) was defined as which could be obtained at equality if we achieve the accuracy of T in a single leaf. We add that this is equivalent (by definition) to lb guess (s a ) = 1 N |s T,incorrect ∩ s a | + λ.
• We additionally define t * (s a , d, λ) as an optimal solution for subproblem s a , depth limit d, and regularizer λ (that is, the solution found when we do not use lower bound guessing). When we just specify t * without arguments, we are referring to a solution for the root subproblem (the whole dataset), with the depth limit argument provided for the tree as a whole.
• We also define R(s a , d, λ) as the objective of the optimal solution found for subproblem s a , depth limit d, and regularizer λ (that is, the objective of the solution found when we do not use lower bound guessing): • Define lb max (s a , d, λ) as the highest lower bound estimate that occurs for a given subproblem s a , depth budget d, and regularization λ, across the algorithm's whole execution when using lower bound guessing (that is, the highest value of lb current from the steps outlined in 4.3). Note that because when a subproblem is solved, the current lower bound is made to match the objective of the solution returned for that subproblem. As a reminder, R guess is computed after the subproblem is solved. When using lower bound guesses, it is possible for intermediate lower bound estimates (and therefore lb max ) to exceed R guess (s a , d, λ), and then the lower bound (but not lb max ) is decreased to match the objective of the best solution found when the subproblem is solved.
Before beginning the proof, recall the steps described in Section 4.3, which apply regardless of the particular search strategy used.
Proof. Without loss of generality, select a tree t that is within some depth constraint d. We wish to prove that the risk on the full dataset (with some regularization λ) is bounded as: or, equivalently, (defining s all as the set of all points in the dataset): To show this, it is sufficient to show a result that is strictly more general. Specifically, we show that for any subproblem s a (with d, λ ≥ 0) that occurs as an internal or leaf node in t (including the root), we can bound lb max (s a , d, λ) as follows. Equation (6) is a direct consequence, using s a as the full dataset s all .
What we originally wished to prove then follows from noting that, by definition of lb max , we have R guess (s all , d, λ) ≤ lb max (s all , d, λ). Here, d, λ are the depth limit and regularization provided for t guess (where d matches or exceeds the depth of t).
We prove this sufficient claim (hereafter referred to as Equation 7) for all subproblems in t using induction.
Base Case: Let us take any subset of data s a , depth constraint d, and regularization λ which corresponds to a subproblem in tree t whose solution in t is a leaf node. Because the solution to s a was a leaf in t, then its objective (without making further splits) is ub = 1 N ( i∈sa 1[y i =ŷ t i ])+λ·1. We want to show, in this case, that (7) holds.
Our initial lower bound guess is lb guess . Either lb guess > ub, or lb guess ≤ ub. If lb guess > ub, we are done with the subproblem as per Step 1 in the Branch-and-Bound algorithm. Otherwise, when lb guess ≤ ub, we know from Step 2b that the lower bound can never increase above ub. Therefore, the highest value of the lower bound during execution, lb max (s a , d, λ), obeys lb max (s a , d, λ) ≤ max(ub, lb guess ). Then, lb max (s a , d, λ) ≤ max(ub, lb guess ) (by argument just above) 1 N |s T,incorrect ∩ s a | + λ (by definition of ub and lb guess ) Note that both terms inside the max are at most i∈s T ,correct ∩sa 1[y i =ŷ t i ] + |s T,incorrect ∩ s a |. Therefore, Moreover, the number of leaves in the optimal tree for subproblem s a is 1, i.e., H ta = 1 (since s a corresponds to a leaf in t), so And this matches Equation (7), as required. Thus, we have shown that the base case obeys the statement of the theorem.

Inductive
Step: Let the set of points s a , depth constraint d > 0, and regularization λ ≥ 0 be a subproblem that corresponds to an internal node in t. Let j indicate the feature that was split on in t for this node, and define s j as the set of data pointsx i such thatx ij = 1 and s c j as the set of data pointsx i such thatx ij = 0. We assume (7) holds for both the left and right child subproblems and aim to show that it holds for their parent subproblem. The left subproblem is s a ∩ s j with depth d − 1 and the right subproblem is s a ∩ s c j with depth d − 1. Thus, assuming (as per the inductive hypothesis) that (7) holds, i.e., it remains to show that Equation (7) holds for s a : We prove the inductive step by cases: 1. If ub ≤ lb guess + λ, then as per Step 1 in our branch-and-bound algorithm, s a corresponds to a leaf in t guess , with a loss for this subproblem equal to ub. Since the algorithm returns immediately after changing the lower bound to ub, the maximum value the lower bound takes (that is, lb max ) is whichever of lb guess or ub is higher. We have: lb max (s a , d, λ) ≤ max(lb guess , ub) ≤ max(lb guess , lb guess + λ) (Since we conditioned on ub ≤ lb guess + λ) ≤ lb guess + λ Noting that because s a corresponds to an internal node in t, there are at least two leaves below it, so H ta ≥ 2. Thus, This equation matches Equation 7, as required. 2. Else, as per Step 2b, the lower bound (and therefore lb max (s a , d, λ)) cannot exceed the combined lower bounds of the left and right subproblems from splitting on feature j. We know the split for feature j will lead to a lower bound estimate no more than lb max (s a ∩ s j , d − 1, λ) + lb max (s a ∩ s c j , d − 1, λ). Thus we have: . Using the inductive hypothesis, this reduces to Noting that s a ∩ s j and s a ∩ s c j partition s a : This equation matches Equation (7), as required. (Although we also need to consider the case where lb guess never increases by the mechanism in 2b, in this case it never increases above the initial lb guess , and we know from the argument for case 1 that if lb max (s a , d, λ) ≤ lb guess then lb max (s a , d, λ) still satisfies equation (7).) Thus we have proved the inductive step holds for all possible cases. By induction, then, we have proved Equation (7) holds for any internal or leaf node in t.
Since the root node is an internal node of t, we have also proven Equation (7) holds for the root problem. As per the justification given when claiming Equation (7) was sufficient, that also means which is what we wished to show.
A.5 Proof of Corollary 4.3.1 Proof. Using Theorem 4.3, we know that for any tree t within the depth constraint for our problem, and any reference model T (this being a local variable not to be confused with T as defined above), we have: Picking t = t (noting that t is, as required, within the depth constraint for our problem), and picking the reference model T , we have: Since t , by definition, makes the same classifications as T , i∈s T ,correct 1[y i =ŷ t i ] = 0.
Recall by definition s T ,incorrect = {i|y i =ŷ T i }, Noting the definition of L(T ,x reduced T , y) Noting the definition of R(t guess ,x reduced T , y) As in the proof provided in Appendix A.1, we note that when we are buildingx reduced T (the dataset used to construct T ), the stopping condition of column elimination is that accuracy decreases, which is when the loss increases: L(T, x, y) < L(T ,x reduced T , y). Thus, the opposite must always be true as we build T : L(T ,x reduced T , y) ≤ L(T, x, y).

B Experimental Details
In this section, we elaborate on the datasets used in our evaluation, preprocessing on those datasets, and the experimental setup.

B.1 Datasets
We present results for seven datasets: one simulated 2-dimensional two spirals dataset, the Fair Isaac ( . We predict whether an individual will default on a loan for the FICO dataset, which individuals are arrested within two years of release on the Propublica recidivism dataset, whether defendants have any type of charge (that they were eventually convicted for) within two years from the current charge date/release date on the Broward recidivism dataset, whether defendants have any type of charge within four years on the Netherlands dataset, and whether a customer will accept a coupon for takeaway food or a cheap restaurant depending on their coupon usage history, current conditions while driving, and coupon expiration time on two coupon datasets. Table 2 summarizes all the datasets. All the datasets, except spiral, are publicly available, without license. The spiral dataset is a synthetic data set we created; the data are published with our benchmarking infrastructure (see Appendix B.4).

B.4 Software Packages Used and/or Modified
GOSDT: We implemented all three types of guesses in the implementation of GOSDT, using the publicly released code from Lin et al. (2020) (https://github.com/Jimmy-Lin/GeneralizedOptimalSparseDecisionTrees). That code bears no license; we will release our modified version with a 3-clause BSD license. DL8.5 We also implemented guessing thresholds and lower bounds in the publicly available code from Aglin, Nijssen, and Schaus (2020) (https://github.com/aia-uclouvain/pydl8.5). That code bears an MIT license; we will release our modified version under the same license. CART: We run CART using the Python implementation from Sci-Kit Learn. The depth and the minimum number of samples required per leaf node are constrained to adjust the resulting tree size. Born-again Tree Ensembles (batree): We run batree using the publicly available code from Vidal and Schiffer (2020) (https://github.com/vidalt/BA-Trees). We based our benchmarking infrastructure off the tree-benchmark suite of Lin (https://github.com/Jimmy-Lin/TreeBenchmark). That code is currently unlicensed; we will release our modified tree-benchmark with a 3-clause BSD license.

C More Experimental Results
We elaborate on hyperparameters used for reference models and optimal decision tree algorithms. We then present extra experimental results that are omitted from the main paper due to space constraints.
Collection and Setup: we ran the following experiment on the 7 datasets COMPAS, Broward, Netherlands, FICO, Takeaway, Restaurant, and spiral. For each dataset, we trained decision trees using varying configurations. For each configuration, we performed a 5-fold cross validation to measure training time, training accuracy and test accuracy for each fold (except the spiral dataset, which is not used in the tables). Table 3 lists the configurations used for each dataset when training decision trees. For GOSDT, DL8.5, and CART, we set the depth limit from 2 to 5. For GOSDT, since it is possible, we also include the configuration with no depth constraint. For datasets except spiral, we set GOSDT regularizers to be 0.005, 0.002, 0.001, 0.0005, 0.0002, and 0.0001. If 1 sample size < regularizer, we omit the regularizer (except for Broward and Takeaway, where we still include the largest regularization below this threshold, 0.0005). For spiral, we set GOSDT regularizers to be 0.1, 0.05, 0.02, and 0.01. DL8.5 and CART do not have a per-leaf regularization penalty but instead allow specification of the minimum support for each leaf. Hence, we set the minimum support of each leaf in these two algorithms to be sample size × regularizer . For batree, we used the default setting.
For threshold guessing and lower bound guessing, we used a gradient boosted decision tree (GBDT) as the reference model. We trained GBDT using four different configurations: 40 decision stumps, 30 max-depth 2 weak classifiers, 50 max-depth 2 weak classifiers, and 20 max-depth 3 weak classifiers. There are no time or memory limitations imposed on configurations to train the reference models. We selected these hyperparameter pairs since they often generate GBDTs with good accuracy, and different reference models from these hyperparamers result in a different number of thresholds. This allows us to analyze how different reference models influence the performance of trees built upon them (see Appendix C.3, C.4, and D). In practice, a user could tune the hyperparameters of their black box modeling algorithm to favor a specific tradeoff between the number of thresholds and the training performance (the former of these influences training-time performance of our methods). For that reason, if several hyperparameter pairs lead to similar performance, it could benefit computation time to use the hyperparameter that introduce the fewest thresholds. We fix the learning rate to 0.1. Calculations: For each combination of dataset, algorithm, and configuration, we produce a set of up to 5 models, depending on how many runs exceeded the time limit or memory limit. We summarize the measurements (e.g., training time, training accuracy, and test accuracy) across the set of up to five models by plotting the median. We compute the 25 th and 75 th percentile and show them as lower and upper error values respectively. For the spiral dataset, since the training set is the whole dataset, we show the measurements without error bars. Results: Figure 10 shows training and test results on the Netherlands, Broward, FICO, and Restaurant datasets. The difference between the stars and the circles shows that guessing strategies improve both DL8.5 and GOSDT training times, generally by 1-2 orders of magnitude. Moreover, with respect to test accuracy, models trained using guessing strategies have test accuracy that is close to or sometimes even better than that of the black box model.

C.2 Sparsity versus Accuracy
Calculation: We use the same calculations as those mentioned in Appendix C.1. The only difference is that we discarded runs that exceed the 30-minute time limit or 125 GB memory limit. Results: Figure 11 shows the accuracy-sparsity tradeoff for different decision tree models (with GBDT accuracy indicated by the black line). Our guessed trees are both sparse and accurate, defining a frontier. That means we achieve the highest accuracy for almost every level of sparsity. CART trees sometimes have higher accuracy with more leaves on the training set. But these complicated trees are overfitting, leading to lower test accuracy. Batree usually does not achieve results on the frontier.

C.3 Value of Threshold Guessing
Calculations: In this experiment, we summarize the measurements across the set of up to 5 models by plotting the average. If one of 5 folds runs out of time or memory, we mark the result as timeout or memory out on the plot. If the experiment timed out, we analyze the best model found at the time of the timeout; if we run out of memory, we are unable to obtain a model and assign 0.5 to accuracy for visualization purposes. In Tables 4 and 5, we report the mean and standard deviation. Results: Figure 12 compares the training time, training accuracy, and test accuracy for GOSDT and DL8.5 with and without threshold guessing. Two subfigures on the left show that the training time after guessing thresholds (blue bars) is orders of magnitude faster than baselines. Note that all baselines either timed out (orange bars with hatches) or hit the memory limit (grey bars with hatches). Subfigures on the right show accuracy with thresholds guessing (gold) is comparable to or sometimes even better than the baseline (purple), since when the model timed out, we report the best model found, and when the model reaches the memory limit, we are unable to obtain any model. Tables 4 and 5 list the training time, training accuracy, and test accuracy for GOSDT and DL8.5 using different reference models for threshold guessing. For both GOSDT and DL8.5, using threshold guessing often dramatically reduces the training time, with little change in either training or test accuracy. Different reference models introduce different numbers of thresholds in the reduced datasets, thereby influencing the training time and memory usage. Comparing the performance of a single dataset with different reference models, we find little change in test accuracy, but a more complicated reference model can increase training time.

C.4 Value of Lower Bound Guessing
Calculations: we use the same calculations as described in Appendix C.3. Results: Table 6 and 7 list the training time, training accuracy, and test accuracy for GOSDT and DL8.5 respectively using different reference models for lower bound guessing. For both GOSDT and DL8.5, using lower bound guessing after applying threshold guessing can further reduce the training time with little change in either training or test accuracy. Sometimes the training accuracy decreases by 1%, but we still obtain test accuracy close to that of the baseline.      Figure 12: (Value of threshold guessing.) Training time (logscale), training accuracy, and test accuracy for GOSDT and DL8.5 with depth limit 5. Two subfigures on the left compare the training time with (blue) and without (orange) threshold guessing. The reference model training time (in green) is often very small and appears atop the training time with guessing (blue). All baselines (hatched) timed out (orange) or hit the memory limit (grey). Subfigures on the right show accuracy with (gold) and without (purple) threshold guessing. When the algorithm ran out of memory, 0.5 was assigned to accuracy for visualization purposes since no model was produced. The figure shows massive decrease in training time with little change in accuracy. The hyperparameters used train reference models are (n_est and max_depth) = (20,3) for COMPAS and Spiral, (40,1) for Broward and FICO, (50,2) for Takeaway and Restaurant, and (30,2) for Netherlands.    Figure 13: GOSDT and DL8.5 trees on the COMPAS dataset with guessed thresholds and guessed lower bounds at depth limit 3. The reference model was trained using 20 max-depth 3 weak classifiers. λ = 0.001.

C.5 Trees
In this section, we show some trees generated by GOSDT and DL8.5 on COMPAS (Figure 13 , 14, 15, 16) and FICO (Figure 17,18,19,20) using all guessing strategies. GOSDT and DL8.5 with all guessing strategies tend to achieve similar accuracy and sparsity when depth limit is relatively small (depth limit 3). When the depth limit increases to 5, GOSDT and DL8.5 with all guessing strategies still tend to achieve similar accuracy, but the trees generated by GOSDT with all guessing strategies tend to be sparser than those generated by DL8.5 with all guessing strategies.

D When Guesses are Wrong
At this point, we have demonstrated the benefit of guessing, but what happens when guesses are wrong? We demonstrate the impact of poor threshold and lower bound guesses by running an experiment using all datasets and the configurations listed in Appendix C. On most datasets, we do not lose accuracy when using any of our four different reference model configurations.
The spiral dataset provides one example where bad guesses affect accuracy. Calculation: We summarize the training accuracy, training time, and number of leaves for the models. Since we do not use 5-fold cross validation for the spiral dataset, we do not include the variability measure. Results: Figure 21a shows examples of guesses that prune too much of the search space. A variety of configurations lead to orders of magnitude reduction in training time. However, GOSDT and DL8.5 trained with a reference model of 40 decision stumps can lead to worse sparsity/accuracy tradeoffs than GOSDT and DL8.5 without guessing. Similar patterns hold for lower bound guesses (see Figure 21b bottom left). But GOSDT and DL8.5 trained using a reference model with 20 max-depth 3 weak classifiers are comparable to the baselines. This phenomenon is easily explained by noting that the reference model with 40 decision stumps has poor performance to begin with, e.g. 0.75 accuracy. The decision trees found with this reference model, although low in accuracy, remain as good as the performance of the reference model (in this case, even better!). Though we provide worst case bounds in terms of how far the decision tree will differ from the reference model, we do not guarantee that we find a strong tree unless the reference model is strong. Any practitioner using our approach should make sure that the reference model is accurate enough not to misguide the search.

E Threshold Guess by Explainable Boosting Machine (EBM)
Section 4.1 introduces how we guess thresholds using GBDT as a reference model. In this appendix, we propose another threshold guessing strategy using the explainable boosting machine (EBM) 1 . EBM (Lou, Caruana, and Gehrke 2012;Caruana et al. 2015) is a generalized additive model (GAM) which is learned using a shallow bagged ensemble of trees on a single feature in each step of stochastic gradient boosting. This GAM model generally has accuracy comparable to the state-of-the-art black-box models like random forests and boosted trees while still maintaining high interpretability. Since EBM can visualize shape functions of each feature, we can easily see the contribution of a single feature to the prediction. Some visible jumps in these shape functions are very informative (Caruana et al. 2015). We can use the thresholds where the shape function jumps as our guess: First, calculate the difference of scores between two neighboring thresholds for each feature. Second, for each feature x ·,j , select thresholds where the difference is larger than tolerance × maxj variable importance (x·,j ) variable importance (x·,j ) , where the variable importance is calculated as the average of the absolute predicted value of each feature for the training dataset. That is, if a feature is less important overall, the thresholds should have larger jumps in order to be selected. There is no restriction for tolerance, and in this experiment, we set it to be either 0.1 or 0.08. Collection and Setup: We ran GOSDT with a GBDT reference model trained using 40 decision stumps and GOSDT with a EBM reference model trained using tolerance 0.1 and 0.08 on the COMPAS and FICO datasets. We ran this particular experiment on a 2.7Ghz (768GB RAM 48 cores) Intel Xeon Gold 6226 processor. We set a 30-minute time limit and 200 GB memory limit.      Calculations: We use the same calculations as those mentioned in Appendix C.2. Results: Figure 22 shows the sparsity accuracy trade-offs for GOSDT with EBM threshold guessing and GBDT threshold guessing. Both guessing strategies can help GOSDT achieve accuracy comparable to GBDT with 100 max-depth 3 weak classifiers (black dash line). Two subfigures on the left show that GBDT-based threshold guessing is better than EBM-based threshold guessing when considering training accuracy.

F FICO Case Study
A decision tree is a special type of decision set. In this appendix, we transform some trees we trained using GOSDT on the FICO dataset to decision sets and compare these transformed decision sets with boolean rules learned by Dash, Gunluk, and Wei (2018) 2 . For simplicity, we call our algorithm CGrules. Collection and Setup: Details about training GOSDT with all guessing strategies were introduced in Appendix C. To train CGrules, we used two different configurations: 1) All parameters were chosen to be their default values, including the way of binarizing features. We denote CGrules with this configuration as CGrules-default. 2) All parameters were chosen to be in the default setting except two model complexity parameters which penalize the number of clauses in the rule and the number of conditions in each clause. We set these two parameters to 1e-7. We denote CGrules with this configuration as CGrules-cp. We ran this particular experiment on a 2.7Ghz (768GB RAM 48 cores) Intel Xeon Gold 6226 processor. Results: Table 8 shows decision rules learned by CGrules and GOSDT with all three guessing strategies. The model from CGrules trained using the default setting is very sparse, consisting of only one clause with two conditions. Compared to the rules trained by CGrules-cp, a depth-2 GOSDT tree is simpler but achieves higher accuracy. A depth-5 GOSDT tree, though more complicated than the others, has the highest accuracy.

G Formal Description of Modifications to Branch-and-Bound Algorithms to Use Lower Bound Guessing With a Reference Model
Below is the full description of the DL8.5 algorithm, exactly as provided in (Aglin, Nijssen, and Schaus 2020), except for the modifications shown in red to support lower bound guessing. We use the same notation as in the original DL8.5 paper, additionally defining T as the reference model for lower bound guessing. The resulting algorithm supports branch and bound decision tree optimization with lower bound guessing. We refer to (Aglin, Nijssen, and Schaus 2020) for detailed explanation of the notation used in this algorithm.  return BestTree(init_ub, make_leaf(I), leaf_error(I)) 8: solution ← cache.get(I) 9: if solution was found and ((solution.tree = NO_TREE) or (init_ub ≤ solution.init_ub)) then 10: return solution 11: (τ, b, ub) ← (NO_TREE, +∞, init_ub) 12: for all attributes i in a well-chosen order do 13: if |cover(I ∪ {i})| ≥ minsup and |cover(I ∪ {¬i})| ≥ minsup then (support is sufficient along both branches) 14: sol 1 ← DL8. if feature_error ≤ ub then (we have a new current best) 23: τ ← make_tree(i, sol 1 .tree, sol 2 .tree) 24: b ← feature_error 25: ub ← b − 1 (we must get at least one more point correct in order to change the bound later) (make DL8.5 notation consistent with our notation) let s I be the indices of the dataset captured by itemset I, that is, s I := cover(I), and then let lb guess (s I ) = 1  Figure 22: Sparsity versus accuracy for GOSDT with EBM threshold guessing and GBDT threshold guessing. Two different tolerances (0.1, 0.08) were used for EBM threshold guesses. 40 decision stumps were used to train GBDT reference model. The black dash line is a GBDT with 100 max-depth 3 weak classifiers.
For DL8.5, the modifications we actually need to make are are somewhat simpler than might be expected from the description in Section 4.3, since DL8.5 does not use a per-leaf penalty λ = 0, and normally sets the lower bound for each subproblem to 0 (as in line 26, which only decides that splitting on a certain feature is better than splitting on any other possible feature when the error is 0). We adjust to calculate a lower bound using our guessing approach (with λ = 0), and choose for our split the first feature that does as well or better than the guessed lower bound.
Below are several functions from the GOSDT algorithm, exactly as provided in (Lin et al. 2020), except for the modifications shown in red to support lower bound guessing. We use the same notation as in the original GOSDT paper, additionally defining T as the reference model for lower bound guessing. The resulting algorithm supports branch and bound decision tree optimization with lower bound guessing. We refer to Lin et al. (2020) for detailed explanation of the notation used in this algorithm, and for the full description of the algorithm (we do not include functions that do not need modifications to support lower-bound guessing).
The modifications to support lower bound guessing are quite simple for GOSDT as well -we simply replace the previous lower bound calculation with our guessed calculation (and account for the potential of the lower bound exceeding the actual solution by changing an = sign to a ≥ sign). The complexity of the modifications listed in Section 4.3 result from accounting for the effects this relatively small code change can have on the algorithm's behaviour. Because branch and bound approaches to decision tree optimization can work on subproblems in a variety of different orders and can cache intermediate results, changing the lower bound calculation requires us to account for the effects of these adjusted lower bounds when searching through subproblems in almost any order.
The coded implementation of GOSDT with lower bound guessing we provide differs slightly from this algorithm, because the public code base for GOSDT continued to evolve after the submission of the GOSDT paper, and now differs slightly from the algorithm described herein. We refer to the codebase itself for details on these differences, most of which are minor. We do highlight one significant difference -GOSDT's new codebase features a notion of "scope" for each subproblem, which prevents the algorithm from exploring one half of a split if the other half has too high a lower bound. We originally allowed scope to be used alongside lower-bound guessing (doing so is consistent with how we describe lower bound guessing, and does not change the validity of our proofs on bounding the maximal inaccuracy). However, we found that when we allowed scope to be used alongside lower-bound guessing, it led to difficulty with verifying the correctness of our implementation. The right child of a split might be excluded from the search space because the left child of that split had a high guessed lower bound, but if we later found that the left child's lower bound guess was too high and decreased the lower bound, GOSDT would not re-enqueue the  Table 8: Comparison of CGrules and GOSDT trees with all three guessing strategies. All decision rules are shown for the 5 th fold. The reference model for GOSDT was trained using 40 decision stumps.
right child. That is not a violation of our lower bound approach (we simply used guessed lower bounds to prune the search space, and it can be shown that Theorem 4.3 still holds with this strategy), but GOSDT's normal error-checking functions would occasionally report that GOSDT failed to converge when this happened. Rather than suppressing these errors, we chose not to base scope off of the guessed lower bound, but rather to base it off of the equivalent points bound (see Theorem B.9 in Lin et al. 2020), which is provably never an overestimate of the lower bound.

H GOSDT with all guessing strategies versus optimal classification trees
In this appendix, we compare GOSDT with all three guessing strategies to the product optimal decision trees provided by interpretable AI with an academic license. We do not know how this algorithm works, and it is not publicly available without a license. The website suggests that the technique is related to OCT (Bertsimas and Dunn 2017), thus we label it OCT in our plots; however, the OCT algorithm of Bertsimas and Dunn (2017) is extremely slow, so we do not know whether a similar approach is used in interpretable.ai's software. Collection and Setup: We ran GOSDT with a GBDT reference model trained using 40 decision stumps and OCT on the COMPAS and FICO datasets. The corresponding depth limit and regularizers for these two datasets are in Table 3. We ran this particular experiment on a 2.7Ghz (768GB RAM 48 cores) Intel Xeon Gold 6226 processor. We set a 30-minute time limit and 200 GB memory limit. We set complexity parameters cp and depth in interpretable.ai's software to the same values of regularizers and depth limits in Table 3 and left all other parameters in default. Calculations: We use the same calculations as those mentioned in Appendix C.2. Results: Figure 23 shows the sparsity and accuracy trade-offs for GOSDT+guessing and OCT. The test performance on both datasets is similar, though it appears that the larger OCT models tended to overfit (training accuracy improved while test accuracy stayed the same), whereas the GOSDT+guessing models did not have this problem. This is possibly because GOSDT+guessing used a reference model that did not overfit, so when GOSDT+guessing matched its performance, it also did not overfit. The major difference between the performance of the algorithms was that on both datasets, GOSDT+guessing was faster to converge. Figure 24 shows the time in seconds versus accuracy for GOSDT and OCT. The brown dots to the left illustrate that GOSDT was generally faster than OCT to get to the same level of accuracy. Thus, GOSDT+guessing yields several advantages over OCT.
(3) Its solutions come with guarantees on performance, whereas OCT (as far as we can tell) does not.