A Scalable Deterministic Global Optimization Algorithm for Training Optimal Decision Tree
Authors: Kaixun Hua
Jiayang Ren
Yankai Cao
Venue: NeurIPS 2022 Accept (2022)
Keywords: optimal decision tree
branch and bound
mixed integer programs
grouping decomposition
sample reduction

Abstract: The training of optimal decision tree via mixed-integer programming (MIP) has attracted much attention in recent literature. However, for large datasets, state-of-the-art approaches struggle to solve the optimal decision tree training problems to a provable global optimal solution within a reasonable time. In this paper, we reformulate the optimal decision tree training problem as a two-stage optimization problem and propose a tailored reduced-space branch and bound algorithm to train optimal decision tree for the classification tasks with continuous features. We present several structure-exploiting lower and upper bounding methods. The computation of bounds can be decomposed into the solution of many small-scale subproblems and can be naturally parallelized. With these bounding methods, we prove that our algorithm can converge by branching only on variables representing the optimal decision tree structure, which is invariant to the size of datasets. Moreover, we propose a novel sample reduction method that can predetermine the cost of part of samples at each BB node. Combining the sample reduction method with the parallelized bounding strategies, our algorithm can be extremely scalable. Our algorithm can find global optimal solutions on dataset with over 245,000 samples (1000 cores, less than 1% optimality gap, within 2 hours). We test 21 real-world datasets from UCI Repository. The results reveal that for datasets with over 7,000 samples, our algorithm can, on average, improve the training accuracy by 3.6% and testing accuracy by 2.8%, compared to the current state-of-the-art.

A Scalable Deterministic Global Optimization Algorithm for Training Optimal Decision Tree
Kaixun Hua University of British Columbia kaixun. hua@ubc.c.c ca
Jiayang Ren
University of British Columbia rjy123070mail ubc. ca
Yankai Cao
University of British Columbia yankai caolubc.ca
Abstract
The training of optimal decision tree via mixed-integer programming (MIP) has attracted much attention in recent literature. However, for large datasets, state-of- the-art approaches struggle to solve the optimal decision tree training problems a provable global optimal solution within a reasonable time. In this paper, we reformulate the optimal decision tree training problem as a two-stage optimization problem and propose a tailored reduced- space branch and bound algorithm train optimal decision tree for the classification tasks with continuous features. We present several snuucture-expliiinnn lower and upper bounding methods. The computation of bounds can be decomposed into the solution of many small-scale subproblems and can naturally parallelized. With these bounding methods, we prove that our algorithm can converge by branching only variables representing the optimal decision tree structure, which invariant the size of datasets. More- over, we propose novel sample reduction method that can predetermine the cost of part of samples at each BB node. Combining the sample reduction method with the parallelized bounding strategies, our algorithm can be extremely scalable. Our algorithm can find global optimal solutions on dataset with over 245,000 samples (1000 cores, less than 1 % optimality gap, within 2 hours). We test 21 real-world datasets from UCI Repository. The results reveal that for datasets with over 7,000 samples, algorithm can, average, improve the training accuracy by 3.6% and testing accuracy by 2.8%, compared to the current state-of-the-art.
Introduction
Decision tree, as a typical supervised learning algorithm with strong interpretability. has been applied in wide range of fields. As rule-based inductive model, a decision tree concludes series of decision rules to navigate tasks such as classification or regression. The target of the decision tree is achieve low prediction error while maintaining the low complexity of the decision tree structure. Therefore, modelling decision tree can be treated as an optimization problem that minimizes the training error and the tree complexity. However, even constructing an optimal decision tree with binary class is NP-complete [Laurent and Rivest 1976). Since the first establishment of the decision tree algorithm by (Morgan and Sonquist] 1963 many heuristic algorithms, such as ID3 QQinlan 1986). C4.5 [Quinaan] 1996] and CART [Breiman et al. 1984), are proposed to achieve the optimization target. However, these heuristic algorithms inevitably fall into sub-optimal solutions.
"correpponding author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

A recent study based on a comprehensive benchmark shows that global solutions lead to average
absolute improvements in test accuracy of 15% [Bertsimas and Dunn 2017 Several formulations and algorithms have been proposed to learn optimal decision trees through mixed integer program-
ming (MIP) [Verwer and Zhang. 2017, 2019 Aghaei et al. 2020 Günlük et al., [02T]_ itemset
mining Nijssen and Fromont 2007| Aglin et al.) 2020], tailed branch-and-bound and dynamic
programming [Hu et al. 2019] Lin et al. 2020
Mc Tavish et al. 2022 Demirović et al. 2022 or
SAT Narodytska et al. 2018 Avellaneda
2020
Ordyniak and Szeider 202 Hu et all, 2020 Shati
et al. 2021]. However, a majority of these works can only address binary features. Binary encoding
(converting continuous features into binary features) may lead to enormous feature space, and may also lose information on the relationship between values of numerical features. Some of the aforementioned works have also proposed several approaches, such bucketization (Verwer and Zhang. 2019], minimum description length principle [Demirović et al., 2022), and boosting tree based column elimination [McTavish al. 2022 deal with this problem.
Besides the works using binary-encoded features, the other research direction that focuses on directly addressing numerical features through MIP is rarely explored. Bertsimas and Dunn (017) propose seminal work on modelling the optimal classification tree (OCT) as a MIP problem, which directly address continuous features. This approach avoids the drawback of binary encoding and can be extended naturally to the multivariate (oblique) decision tree problem [Bertsimas and Dunn 2019]. Recently, Zhu et al. (0200 present an SVM-based MIP formulation for learning optimal multivariate decision trees. This work also presents a sample selection method to select a subset of samples and use it to train the decision tree. Although the authors claim that the sample selection method can handle large datasets, the decision tree learned on the subset is not guaranteed to be the optimal one of the original dataset. The above MIP based approaches all rely off-the-shelf MIP solvers such as CPLEX [Cllex 2020 and Gurobi [Optimization, 2020]. and have reported directly addressing datasets with up 7,000 samples. Bertsimas and Dunn [017 mentioned in their article that "datasets with tens of thousands of points were tested, but the time required for our methods to generate high- quality solutions was prohibitive". The main obstacle preventing the solvable problem from scaling to large datasets is that all these solvers implement a classical branch-and -areh--nn-bbuudd (BB) scheme, which needs to branch on all binary variables to guarantee convergence, the dimension of which expands linearly with the size of the dataset.
In this paper, we propose scalable deterministic global optimization algorithm for training optimal decision tree on classification task with numerical features. The first contribution of our work is that we reformulate the optimal decision tree training as two-stage optimization problem. The stochastic programming community has made great progress in exploiting the structure of this type of problems (Karuppiah and Grossmann, 2008 Li and Grossmann 2019]. Recently, Cao and Zavala (0019 prove that for a two-stage problem with continuous second stage variables, branching only on the first stage variables can guarantee the convergence under mild assumptions. Many machine learning problems can be modeled as a two-stage problem and can apply this reduced-space BB method (Hua al. 202T Shi et al. 2022]. Although for the decision tree training problem, there are both binary and continuous varialees in the second stage (i.e., sample specific variables, such as the predicted algorithm can still be guaranteed by only branching on the first-stage variables (i.e., variables that represents the structure of the decision tree), the dimension of which is independent of the number of samples. Secondly, we provide several bounding strategies to construct the lower and upper bound of each BB node. Our new MIP formulation consists of a decomposable structure that can be directly parallelized when solving the lower bounding problem. We also present tight and efficient MIP formula to obtain lower bound quickly. Thirdly, we develop a sample reduction method that can predetermine the costs of some samples before the lower bound calculation at each BB node. Such a method can be combined with the lower bound calculation to further speed up the solution process, especially for large-scale datasets. The ablation test (Appendix DD) performed on datasets reveals consistant effecttivnness on improving the computation speed of the BB process. Our experiments show that some BB nodes (e.g., when training the dataset BANKNOTE) can even have more than 99% of samples to be determined before computing the lower bound.
class of a sample), we prove that the convergence of our branch-and-boung
With these strategies, our tailored reduced-space BB algorithm can scale well on large datasets. For large datasets, the optimal solution found by our algorithm can on average reduce the optimal cost by 12.5% and improve the training accuracy by 3.6% and testing accuracy by 2.8%, compared to the current state-of the [Bertsimas and Dunn 2019 Remarkably, our work is the first that
2

---

successfully trains decision tree to global optimum on a dataset with 245,000 samples (1000 cores, less than 1% optimality gap, within 2 hours). We also improve the test accuracy by 1.7% on a dataset with almost one million samples (928,991 samples, 1000 cores, under 56.2% optimality gap within 4 hours), compared with CART and OCT. We highlight that we also report the optimality gap as a criteria to evaluate the goodness of the optimal solution, which is not presented in the majority of MIP based works. [erttsimas and Dunn 2019 states that the current MIP solvers struggle to provide reasonable optimality gap for their OCT problem. It is also aligned with our numerical analysis that OCT still retains over 90% optimality gap on average for large datasets. At the same time, our algorithm provide practical gap on most of the dataset. Although OCT could find better solution than CART at the early stage of the solving process, our results reveal that an even better solution could be discovered later and can result in better testing accuracy on large datasets.
In the following discussion of the paper, to avoid the ambiguity, we denote the node for the decision tree as decision node and leaf node and the node for the branch-and-hound algorithm as BB node.
2 Optimal Decision Tree with Decomposible Structure
In this work, we focus on training an optimal decision tree for the task of classification. Most part of the formulation presented here follows the work of Bertsimas and Dunn (2019). However, in our formulation, we do not consider the constraint about the minimum number of samples required in the
leaf node, Let = {I,.... ,n) be the sample set and K = {1,-- ................................ } be the class set. For a given data set X = {x. x, E R 8 E S} with corresponding label set Y= [y= yy E (0, 1] E S}. where P is the number of features and K is the number of class. Initially, we scale each feature of the dataset to the range between 0 and 1. We seek to find an optimal decision tree model F R. {0,1] 1] K with maximum depth D, such that:
((F) = Σ E((F(x))y))) + +
(1)
SES
is minimized. Here, E(-) measures the misclassification error, R(-) is the regularization function
that measure the complexity of the optimal decision tree model and À is the complexity parameter.
We denote & {1.... ""} the node of the tree, where T = 2D+1 1 is the size (total number of nodes) of the tree. Following the definition of Bertsimas and Dunn [2077]. let p(t) = [t/2] be the parent decision node of i, (t) as the set of ancestors of whose left branch is followed on the path from root node to node f, and Ax(t) as the set of ancestors of t whose right branch is followed on the path from root node node I. The tree node consists of two sets: decision node
with E Tn = (1,.... [T/2]} and leaf node with E Ti = {LT/2] + 1..., T). The training of optimal decision tree can be treated as an optimization problem (Problem
min I.
EC
1
L.
+
A
Σ d:)
(2a)
L
n TETD
3ES
1
s.t.
(Yok Cki 2yskCke) - L, S 11 - 2st, Vt E T
(2b)
2
kek
Σ
Che 11 VLETr
(2c)
kEK
Σ Est= =1
(2d)
tET2
am (x, + - Emin) + Cmin I bm + (1 + Cmaz) (1- - 22t), Vm E (t)) E Tr
(2e)
a X2 2 bm (1 2st,, Vm An(t), t E T
T
(2f)
P
Σ ajz = de, Vt TD.j E (1,.... P)
(2g)
j=1
0 0 b, S de, Vt To
(2h)
d, S d
Vt #eT To
(2
0 3. 51
(2))
3

---

aj,, d E (0.1),0 I b, = E TD.j Est: Okt E (0,1), ve
(2k)
(21)
8 SES
(2m)
Here, variable a, b, d describe the structure of decision tree. Specifically, variable d, node t E TD determines whether a decision node splits or not. We track such split with variable a = [01e,".. "rr]"""" E {0. 1) and b, E [0. 1]. The prediction of each leaf node is controlled by the class indicator Ckt E {0. 1). Vt E Tr,k E K. Variable 2xt, Vt E TL. E S represents whether sample falls into leaf t. Variable L, E [0, 1] represents the loss of sample Usk {0, 1] is the element of vector ys which represents whether sample s labeled k. L the parameter to normalize the misclassification with the baseline accuracy.
Cmaz. and Emin are constants to maintain the calculation stability of problem 2 Their values are generated following [Bertsimas and Dunn 2019 A detailed explanation of constraints can be found in Appendix A at supplementary materials.
3 Reduced-space Branch-and-Bound Algorithm
In this section, we model Problem2 as a two-stage optimization problem and propose a reduced-space branch-and-bound (BB) algorithm with properly designed lower and upper bounds. Algorithm [] (presented in Appendix B) elaborates the details of our algorithm. The algorithm starts from the initial feasible region Mg- It narrows the gap between the lower and upper bound by partitioning Mo recursively into smaller regions and pruning any regions that are verified to contain no optimal solution. In each iteration with particular sub-region M, lower bound ((M) and upper bound a ((M) are computed. If the gap between 3 and a is smaller than e, Algorithm I terminates. Otherwise M is partitioned into two disjoint sub-region with some branching strategies explained in Appendix [3.2]
A critical feature of our algorithm is that it can ensure the convergence by only branching on the first stage variables (i.e. a, a,b,c c, d). Cao and Zavala [2019) prove that for two-stage optimization problem, if the second stage variables are continuous, then the BB algorithm can converge by branching only on the first stage variables. Although the decision tree training problem is different since we have both continuous and binary second stage variables, we can still prove its convergence.
Theorem 1. Algorithm 1 converges to the global optimum, in the sense that
lim a 20000
lim 3r = 11000
(3)
The proof of Theorem is presented in Appendix B.I
3.1
Two Stage Optimization Problem
Note that variables a, b, c, describe the structure decision tree and are the same for all sample, while variables z and L are sample-specific variables and describe the allocation and cost of specific sample. Therefore, Problem can be reformulated as a two-stage optimization problem in the following form:
f(Mo)
min (.)(m)
(4)
Me SES
where we denote (a, b, c, d) as all first-stage variables and Q+(-) represents the optimal value of the second-stage problem:
(m) = min
L Σ de
(5a)
T,
ICTD
s.t. Constraint 20
21
(5b)
The closed set Mo [mm m²) denotes the region of the first stage variables. (1), (-)s represent the lower and upper bound of each variable. In each BB node with a specific partition M C Mo. we solve the problem f(M)= min Σ (m).
mEM SES

---

3.2 Lower Bounding Problem
the problem we solve at each BB node has an implicit constraint. That is, all samples share the same first stage variables (i.e., tree structure). This is called non- anticipativity constraints in the stochastic programming community. We can obtain a basic lower bound by relaxing this constraint and solve the resulting problem:
Basic lower bounding problem:
B(M) ==
min Σ (m.)) M.EM #ES
(6)
such problem can be easily decomposed into n subproblems (.( == min Qa(m) with (MM)
MEM
Σ (M). The optimal value of B, can be calculated through Algorithm (presented Appendix sES
by enumerating all possible leaf nodes that sample s can fall into, without the need to solve any
optimization problems explicitly. The complexity of Algorithm 2 is O (Tz)). Since the depth
of the tree is typically small for the sake of interpretability, the speed of Algorithm can be executed much faster than other methods.
Theorem 2. With given bound = = [m',, m"), Algorithm 2 finds all possible leaf nodes that sample s can fall into and gives the global optimal value of B. (M)).
The proof of Theorem in Appendix
One byproduct of Algorithm is Te, S. Tz. the set of all possible leaf fall into. Figure in Section provides an example on the determination of Tz,- We have ~nt- = 0, vt & Tz.- For each sample, basic lower bounding method computes the lower bound by comparing the label Vsk with the prediction Cke of each leaf node in E T Note here basic lower bounding method relaxes the non-anticipativity constraints on c and allow different values of e for each sample. We can enforce this constraint generate tighter lower bound by solving the following MIP problem:
Relaxed MIP problem:
nodes that sample
B²(M) min o,L
Σ -
I. + EL
Σ d 1ETD
(7a)
3ES
s.t. L, 21 Σ Σ
yokCkt
(7b)
1ET,, kEK.
Σ Cht =1 1, Vt Tr
(7c)
kEK
0 L, 1
(7d)
Ckt E (0, VI TT,
(7e)
S
(7f)
where d' is the lower bound of variable d. Since the only number of integer variables in Problem c. the dimension of which is typically small and independent of the number of samples, solving
Problem 7 is much easier than the original problem. Because Problem 7 is based on the Tz, calculated from the basic lower bounding method but enforces non-am con-anticipativity constraints on c, we have: Proposition 3. B(M) < (M) S(M)
Notice that when the variable e fixed (c' = c² in M) at BB node. 3(M) (M)) holds and we do not need to compute (MM)..
Group decomposition: for the basic lower bounding method, treat each sample as subproblem. One natural extension to assign multiple samples to a subproblem. Specifically, we define the
group set G = {l. ,G), and we partition S into G groups {Si....,Se Ü S = and
g=1
S, S,S = 0. Vi.g E g. # g). then we can obtain a lower bound from:
8 (M)
min (g)))))
(8)
my EM
gEg
5

---

which can be decomposed into G subproblems with (M) - Σ
(M) (M and (M
DEG
min (g())) Here each subproblem 9 can be obtained by replacing E S in the original myeM
problem with s Sg. The non non-anticipativity constraints is still enforeed within each subproblem (i.e. a, b, c, d are the same for all samples within the group), while the con-anticipativity constraints between groups are relaxed. Hence, the d provides a tighter lower bound than the basic lower bound B.
Proposition 4. B(M) S (M) S S(M)
The fewer groups we split, the tighter is the lower bound. However, the solution time of each subproblem is also longer. Therefore, there is a trade-off between the efficiency and tightness when setting the number of groups. Besides this, the way of assigning samples to groups also influences the quality of lower bounds. Finding the best grouping scheme is itself NP-hard. In our implementation, we adopted the heuristic results (e.g. CART) to navigate the assignment of groups. First, we divide all samples into raw groups based on leaves they fall under from the heuristic solution. Second, in each raw group, a k-maass clustering is launched. Finally, the samples for each cluster at each raw group are evenly assigned to G' groups. In this way, samples are approximately evenly distributed among different groups. We keep the group assignment the same for all BB nodes.
3.3 Upper Bounding Problem
The upper bound can be easily obtained by choosing any arbitrary first stage solution in E M. Let ((M) be the upper bounding problem, have a (M) = Exes Q, (m)) The calculation of a(M) is the same the evaluation of decision tree mi, which is computationally cheap. In our implementation, at the root BB node, we use CART to provide a feasible solution mn for the initial upper bound. We also propose two heuristics in each descendent BB node enable fast search for an optimal solution. First, the optimal solution to each subproblem directly provides a feasible solution. We calculate the corresponding cost and pick the most optimal one to be the upper bound. This method does not require additional computational time to generate m.. However, it could be affected by the group assignment. The second method applies bootstrapping to randomly generate a small subset of samples and train decision tree for the subset. This "bootstrapped" subproblem provides a feasible solution and introduces more possibilities for finding a better upper bound.
4 Sample Reduction
During the calculation of the basic lower bound, Algorithm reduucs the possible leaf nodes that sample s can fall into from Tr Tz Comparing the label ysk with the range of c of each leaf node in E Te.. the loss of some samples can be determined. Specifically, suppose & is the label of sample (i.e. Ysk 1). Equation 9 checks the loss of sample under M.
1
if A des = cht =
1ET,, if
L.
0
A Cks che
LET.,
undtm. otherwise
Figure provides an example to illustrate the determination of Tz, and the loss determination of a sample s under some conditions of ce, If the loss of sample is determined at the current BB node, we no longer need to take this sample into consideration in the lower bound calculation, resulting in sample reduction. Moreover, determined loss holds for all descendent BB nodes. Therefore, the determination of some sample's loss can significantly reduce the computational load, especially when the level of the search tree goes deep. With sample reduction, many of these samples can determine their loss without being involved in the solution of any optimization problem. Indeed, for dataset SKIN-SEGMENTATION (one of the largest test dataset in our experiment with n = 245, 057), on average, 63.6% of the samples can be determined among all BB nodes. For some BB nodes, 99.6% of samples can have their loss determined. Such a strategy significantly improves node exploration efficiency.
We notice that a similar "data selection" method is proposed (Zhhu et al. 2020 major difference between their method and our "cost determination" method is that the solution found from the

---

"selected" data subset can not guarantee the global optimum of the original dataset. In contrast, in our method, the loss of removed samples not deleted but pre-determined and added the final total loss calculation. Hence, the optimal solution we obtain is the same as the optimal solution of the original problem.
Improvements on the calculation of lower bound: define the sample set with determined loss as Sat and those with undetermined loss as Sud, such that |Sal + [Sual = n. Here, we analyze the effects of sample reduction combined with the reach-leaf determination (T=,) on three lower bound strategies. Initially, the calculation of the basic lower bounding problem requires running Algorithm 2 for n times. With sample reduction, the basic lower bounding problem (Problem 6 can be rewritten as:
Σ (o( - - E
3(M) == min M.
(10)
SESuA
SESa
Here, L., Vs E Sat is already determined at the parent BB node via the sample reduction. Thus, the computing load of Problem can be reduced from Onn) to O[[Sua)) Since M of descendent BB node is subset of its parent BB node, Ts, can also be inherited from the parent BB node, and the calculation of Tz, only need to be executed on samples in Sud. Similarly, for the lower bound from relaxed MIP, the number of samples involved in the optimization is reduced from for the group decomposition based lower bounding strategy, the number of samples involved each subproblem is reduced from |Sy to (Snd O Syl- The detailed formulations of these lower bounding methods after sample reduction can be found in Appendix D
[Sua]- Finally,
x1 = [0.8). y1 = [0,
X2 = [0.5]. = [1.
X3 = [0.3]. y3 = [0. []
0.0
01
01
01
01
011
011
0.0
01
01
01
11
01
01
01
11
01
01
01
11
01
01
(a) To = [6, 71,
= 0
(b) T2 = [5, 65,6,77 7]. L2
=1
(c) T. = [1,5, 6, 71, La undtm
00.1.001,0.11)66- [0.6, 0.4, 1. = [ c = [1]] The nodes blue indicate the possible paths of sample under current bound. The bound of for each leaf is denoted - under each leaf node. Sample 1: since [1] 2 6%. X1 can only fall into the right descendent of the root decision node, and as x1 [1] E [b4, bg]. leaf node and can be reached by sample and thus Ts {6, 7). Since dhe = cht 1, vl Tz, (colored in blue), which identical to y/2, have L1
Figure 1: Loss determination under the bounds a'= =
=
Sample 2: since
xg[1] E [b}, 61.. X2 can fall into both descendent of the root decision node, However, x²[1] > by. leaf node can not be reached by sample 2, and thus Tz, = (5, 6, 7}. Since y2 is inconsistent with all the [c4, cf), Vt Tzyx we determine that L2 = 1. Sample 3: since xa[1] E b8]. Vi E TD. all leaf node can be reached by sample 3, Tzg {4,5, 7). Sample 3 can have several possible loss values fall into different leaf node Tag. Here, variable e is fixed in all leaves except leaf (colored in red). Therefore,
unable to determine Lg.
5 Computational Experiments
We evaluate the performance of our algorithm (denoted as RS-OCT) on 21 real-world datasets from UCI machine learning repository [Lichman et al., 2013). The algorithm is implemented in Julia 1.7.0. Our implementation code is available at: https: //t::/giitutt com hat//aaaaaaaaaaaaaaaaaaa opt imal decisioon Comparison is made against the CART algorithm [Breiman et al.) 1984 and Optimal Classification Tree (OCT) method [Bertsimas and Dunn 2017]. A comparison with the performance of FlowOCT [Aghaei et al., 2020 also presented in Appendix [..T To avoid the effects of hyper-paramete choice, the penalty parameter À is set to 0.05 for all three algorithms. The split of training and testing data follows the work of Bertsimas and Dunn
(0077). that is, 75% of the entire dataset is selected as the training set while the rest 25% is set as the testing set. All datasets
7

---

split by the stratifiedobs function from Julia Package MLDataUtils, under random seed 1, so that the distribution of class is guaranteed to be the same both training and testing set. RS-OCT and OCT are executed until either they converge to an optimality gap within 1% or the runtime exceeds a limit of 4 hours. The result of CART obtained through the Julia Package DecisionTree with version 10.10.15 12. The MIP problem of OCT and the subproblem of RS-OCT (for grouping based lower bound) are solved by the statc-of-art global optimizer CPLEX 20.1.0 [Cplex 2020]. Both OCT and RS-OCT are provided with the same CART solution as warm-start. A preliminary parallel version of our algorithm is implemented by assigning subproblems in the lower bound calculation to multiple CPU cores. The size of each subproblem for group decomposition is set 2n n
as max(2K, [ct+++2)-22 (22 ). where of (default: 1,50) is constant that controls the average group-size. The serial and parallel experiments are executed on a nigh-performance computing cluster (40 Intel "Skylake" at 2.4 GHz with 202G RAM per computing node). Five criteria (upper bound, training accuracy, testing accuracy, optimality gap, and time) are used to compare the performance of the algorithms. Here, the upper bound (UB) represents the best feasible solution we found until the termination of each algorithm. The optimality gap is calculated as UB-LB x 100%. It measures the closeness from the best-searched solution (i.e. UB) to its possible global optimum (i.e. lower bound). As a unique property of deterministic global optimization algorithms, heuristic algorithms like CART cannot provide such criteria. Our work focuses on improving the solution process of the optimal decision tree problem. Therefore, to best represent the solving performance, we use the same value of X, so that both our method and OCT are solving the same optimization problem, and we can have a fair comparison of the optimality gap, solution time, and best achieved upper bound on this specific problem formulation. However, to further demonstrate the performance of RS-OCT in practical, compared to other state-of-the-arr artt algorithms, we also perform experiments with hyperparameter tuning on depth 2 and The results are presented in Appendix E.T The effectiveness of sample reduction is validated via the ablation test and the result is shown in Appendix
0B
Small and medium-scale datasets We perform experiments on 15 datasets ranging from 210 to 5,473 samples. Table Table@preet presents the result of using three algorithms. In terms of UB, RS-OCT can find better (or equally better) solution with the lowest cost for almost all datasets, compared to CART and OCT, RS-OCT also terminates with a smaller optimality gap for all datasets. It is remarkable that for datasets such as GLASS, BANKNOTE, and WALL--FLLL.OWIN RS-OCT can achieve an optimality gap within 1% while OCT still has a large gap over 98% after 4 hours of running. Our result indicates that although OCT could find a better solution than CART, it is still hard to claim that such solution is the optimal one. In contrast, RS-OCT can find an even better solution more efficiently and prove the optimality within reasonable time. Due to the better cost found by RS- RS-OCT, the training accuracy of all datasets in Table improves by 2.9% on average compared to CART and 0.8% on average compared to OCT. In terms of testing accuracy, since we fixed the penalty parameter À for all datasets, the result on smaller datasets (n < 1000) is unsatisfactory probably due to overfitting issue. In total, the testing accuracy is improved by 2.2% and 1 1.0%, on average, compared to CART and OCT, respectively. For medium-scale datasets (n 2 1000), the testing accuracy improves by 3.3% on average compared to CART and 1.4% on average compared to OCT.
Large-scale datasets We test our algorithm on several large datasets (n 2 7, 000), with a variety of dimensions (3-16) and number of classes (2-12), as shown in Table 2 RS-OCT is executed in parallel with 1000 CPU cores. Remarkably, RS-OCT outperforms OCT and CART on all criteria for all datasets, including the HT-SENSOR which has almost one million samples. In terms of upper bound, we notice that for datasets with a size over 40, 000 samples, OCT can not provide a better solution than the warm-start given by CART. Nevertheless, RS-OCT discovers better solutions in terms of UB than both CART 12.5% improvement on average) and OCT (11.7% improvement on average) on all large datasets. In terms of optimality gap. RS- converges to an optimality gap within 1% on PENDIGITS, SHUTTLE, and SEIN-SEMMENTTTOON It verifies that the best solutions found for these datasets are merely at most 1% close to the actual global optimal solution. It the first time an optimal decision tree (without binary encoding) is found for a dataset with almost one million samples with a meaningful optimality gap 2%) in four hours of runtime. Remarkably, our algorithm can also solve for a dataset with over 200, 000 samples to a practical optimality gap (S 1%) in less than two hours. Given the more optimal solution found by RS-OCT, its training accuracy is on average boosted by 3. 7% and 3.6%, compared to CART and OCT, respectively. The testing accuracy
8

---

Table I: Numerical results small and median datasets (7) 2, 0.05, serial). The results of testing accuracy reported in [Bertsimas and Dunn 2017] are also listed the paranthesis for CART and OCT. These "paranthesis" results obtained within the runtime of hours.
DATA- SET
TRAINING ACCURACY($))
TESTING
GAP (%)
TIME (S)
P
K METHOD
UB
ACCURACY($8
CART
42.2
91.2
94.1 (87.2)
SEEDS
OCT
27.2
94.3
86.3 (88.7)
$79.
RS-OCT
27.2
94.3
88.2
<1%
151.2
CART
152.2
65.8
64.3
GLASS
214
6
OCT
143,8
67.7
64.3
99.9
14400
RS-OCT
140.9
68.4
62.5
<1 %
2503.8
CART
74.3
90.0
88.9
BODY
507
2
OCT
58.7
92.1
92.1
<1%
10985
RS-OCT
58.7
92.1
92.1
<1%
965.9
CART
281.6
73.7
71.2 (70.1)
STATLOG-
1,000
24
2
OCT
280.2
73.9
71.2 (70.5)
99.9
14400
GERMAN
RS-OCT
267.3
75.1
72.0
38.5
14400
CART
667.6
62.6
61.9
CONCRETE
1,030
OCT
621.4
65.2
65.4
100
14400
RS-OCT
621.4
65.2
63.0
13.0
14400
CART
185.6
90.0
89.0 (89.0)
BANKNOTE
1.372
155.0
91.6
91.0 (90.1)
98.7
14400
RS-OCT
135.2
92.7
92.2
<1 %
675.6
CART
1353.7
47.6
46.3 (46.8)
CONTRA- CEPTIVE
1,473
OCT
1215.6
53.0
51.0 (48.4)
54.5
14400
RS-OCT
1189.8
54.0
56.4
12.0
14400
CART
103.3
93.1
93.1 (93.1)
OZONE- EIGHT
1.847
72
OCT
102.2
93.2
92.8 (93.1)
100
14400
RS-OCT
94.7
93.7
92.4
97.6
14400
CART
43.5
97.0
96.8 (96.8)
OZONE-
1,848
72
2
OCT
39.3
97.3
96.8 (96.8)
99.9
14400
RS-OCT
40.4
97.2
96.8
99.6
14400
CART
140.6
95.4
95.6 (95.6)
THYROID-
3,772
21
3
OCT
86.7
97.2
96.8 (95.6)
99.9
14400
ANN
RS-OCT
66.1
97.8
98.1
65.4
14400
CART
4861.3
64.7
64.6 (63.2)
STATLOG- LANSAT
4.435
4786.8
65.2
64.8 (63.2)
14400
RS-OCT
4757.8
65.4
66.0
14400
CART
826.9
85.5
84.5 (84.2)
SPAMBASE
4,601
OCT
826.9
85.5
84.5 (84.3)
100
14400
RS-OCT
756.0
86.7
85.9
81.4
14400
CART
608.8
94.0
94.0 (94.0)
WALL-
5.456
OCT 608.8
94.0
94.0 (94.0)
100
14400
FOLLOWING
RS-OCT 608.8
94.0
94.0
<1% %
223.2
CART 315.4
93.1
93.2
PAGE-
5.473
10
5
OCT 273.1
93.9
93.8
100
14400
BLOCK
RS-OCT
209.6
95.4
95.0
46.2
14400
also boosted by 3.3% and 2.8% on CART and OCT, respectively. Notably, compared with the results from Table I we find that the performance of RS-OCT is improving with the increment of the data size.
Conclusion
This paper proposed tailed reduced-space branch and bound (BB) algorithm to train optimal decision tree for the classification tasks. Our BB algorithm can converge to a global e-optimal solution by only branching variables describing the tree structure, which invariant the number of samples. Combined with the sample reduction and paralleled lower bound calculation, our algorithm can perform well on all datasets in terms of UB, optimality gap and training accuracy. Our algorithm also improves the testing accuracy on all large datasets (n 2 7, 000).
Impact and Future work: We hope that the MIP-based scalable framework proposed in this paper can help address the needs of optimal decision tree for large-scale data training high-stake domains such crime analysis (Zhuang et al., 2017), medical decision [Bertsimas et al.) 2018 We look forward integrating our algorithms with other functionality (e.g., fairness Aggaei et al. 2019 to provide handy tools for wider applications.

---

Table 2: Numerical results on large datasets (D = 2, = 0.05, paralleled with 1000 cores).
Bertsimas and Dunn 2017] not report results on datasets of this scale.
DATA
TRAINING ACCURACY($))
TESTING
GAP (%)
TIME
P
K
METHOD
UB
SET
ACCURACY(%))
(S)
CART
$2993.0
38.9
PENDIGITS
7,494
16
10
OCT
32993.0
38.9
39.1
100
14400
RS-OCT
32426.1
40.0
39,9
<1%
2093.5
CART
9454.3
50.4
51.0
AVILA
10,430
10
12
OCT 9196.4
51.7
$2.5
100
14400
RS-OCT
8787.5
53.8
53.8
19.6
14400
CART
7815.8
61.7
61.2
BEG
14,980
OCT
7748.7
61.7
61.0
100
14400
RS-OCT
6752.7
66.9
65.5
50.8
14400
CART
327.0
97.8
97.7
HTRU
17,898
2
OCT
320.5
97.8
97.7
100
14400
RS-OCT
300.7
98.0
97.8
42.8
14400
CART
2567.5
93.8
93.8
43,500
OCT
2567.5
93.8
93.8
100
14400
RS-OCT
1908.1
95.4
95.5
<1%
586.1
SKIN- 245,057
CART 23409.5
89.9
89.8
SEGMEN-
2
OCT 23409.5
89.9
89.8
100
14400
TATION
RS-OCT 16953.7
92.7
92.7
<1%
6698.9
CART 782046.1
58.1
HT: SENSOR
928,991
OCT 782046.1
58.1
58.1
100
14400
RS-OCT
753075.8
59.7
59.7
56.2
14400
Limitation: Similar to other works, our algorithm only tests optimal decision tree problems with small depth (e.g. 3). Larger D slows down the algorithm's efficiency. Proper bound tightening methods will be designed in the future to solve this problem.
Acknowledgments and Disclosure of Funding
Y.C. acknowledges funding from the discovery program of the Natural Science and Engineering Re- search Council Canada under grant RGPIN-2019 The authors also gratefully acknowledge the computing resources provided by SciNet (www.scinethpc.ca) and Digital Research Alliance of Canada (www.allianceaan.ca)
References
Sina Aghaei, Mohammad Javad Azizi, and Phebe Vayanos. Learning optimal and fair decision trees for non-discrininative decision-making In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1418-1426, 2019.
Sina Aghaei, Andres Gomez, and Phebe Vayanos. Learning optimal classification trees: Strong max-flow formulations. arXiv preprint arXiv:2002.09142. 2020.
Gaël Aglin, Siegfried Nijssen, and Pierre Schaus. Learning optimal decision trees using caching branch-and-bound search. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3146-3153, 2020.
Florent Avellaneda. Efficient inference of optimal decision trees. Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pages 3195-3202, 2020.
Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning, 106(7):1039- 1082, 2017.
Dimitris Bertsimas and Jack Dunn. Machine learning under a modern optimization lens. Dynamic Ideas LLC, 2019.
Dimitris Bertsimas, Jack Dunn, Colin Pawlowski, John Silberholz, Alexander Weinstein, Ying Daisy Zhuo, Eddy Chen, and Aymen A Elfiky. Applied informatics decision support tool for mortality predictions in patients with cancer. JCO clinical cancer informatics, 2:1-11, 2018.
L Breiman, JH Friedman, R Olshen, and CJ Stone. Classification and regression trees. 1984.
10

---

Yankai Cao and Victor M Zavala. A scalable global optimization algorithm for stochastic nonlinear programs. Journal of Global Optimization, 75(2):393-416,7 2019.
IBM ILOG Cplex. V20.1.0: User's manual for CPLEX. International Business Machines Corpora- fion, 2020.
Emir Demirović, Anna Lukina, Emmanuel Hebrard, Jeffrey Chan, James Bailey, Christopher Leckie, Kotagiri Ramamohanarao, and Peter J Stuckey. Murtree: Optimal decision trees via dynamic programming and search. Journal of Machine Learning Research, 23(26):1-47, 2022.
Oktay Günlük, Jayant Kalagnanam, Minhan Li, Matt Menickelly, and Katya Scheinberg. Optimal decision trees for categorical data via integer programming. Journal of global optimization, 81(1); 233-260, 2021.
Reiner Horst and Hoang Tuy. Global optimization: Deterministic approaches. Springer Science & Business Media, 2013.
Hao Hu, Mohamed Siala, Emmanuel Hebrard, and Marie-José Huguet. Learning optimal decision trees with maxsat and its integration in adaboost. In IJCAI-PRICAI 2020, 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence, 2020.
Xiyang Hu, Cynthia Rudin, and Margo Seltzer. Optimal sparse decision trees. Advances in Neural Information Processing Systems, 32, 2019.
Kaixun Hua, Mingfei Shi, and Yankai Cao. A scalable deterministic global optimization algorithm for clustering problems. In International Conference on Machine Learning, pages 4391 1-441.. PMLR, 2021.
Ramkumar Karuppiah and Ignacio E Grossmann. A lagrangean based branch-and-cut algorithm for global optimization nonconvex mixed-integer nonlinear programs with decomposable structures. Journal of global optimization, (1(2):163-186 2008.
Hyafil Laurent and Ronald L Rivest. Constructing optimal binary decision trees is np-complete. Information processing letters, 5(1):15-17, 1976.
Can Li and Ignacio E Grossmann. A generalized benders decomposition based branch and cut algorithm for two-stage stochastic programs with nonconvex constraints and mixed-bing -inary first and second stage variables. Journal of Global Optimization, 75(2):247-272, 2019.
Moshe Lichman al. Uci machine learning repository, 2013.
Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo Seltzer. Generalized and scalable optimal sparse decision trees. In International Conference on Machine Learning, pages 6150-6160. PMLR, 2020.
Hayden McTavish, Chudi Zhong, Reto Achermann, Ilias Karimalis, Jacques Chen, Cynthia Rudin, and Margo Seltzer. Fast sparse decision tree optimization via reference ensembles. In AAAI Conference on Artificial Intelligence, 2022.
James Morgan and John A Sonquist. Problems in the analysis of survey data, and a proposal. Journal of the American statistical association, 58(302)445-434, 1963.
Nina Narodytska, Alexey Ignatiev, Filipe Pereira, Joao Marques- Silva, and RAS. Learning optimal decision trees with sat. In Ijcai, pages 1362-1368, 2018.
Siegfried Nijssen and Elisa Fromont. Mining optimal decision trees from itemset lattices. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 530-539, 2007.
Gurobi Optimization. Gurobi optimizer 9.0 reference manual. 2020.
Sebastian Ordyniak and Stefan Szeider. Parameterized complexity of small decision tree learning. Cancer, 18, 2021.

---

J. Ross Quinlan. Induction of decision trees. Machine learning, 1(1):81-100 1986.
J Ross Quinlan. Improved use of continuous attributes in c4.5, Journal of artificial intelligence research, 4:77-90, 1996.
Pouya Shati, Eldan Cohen, and Sheila Mcllraith. Sat-based approach for learning optimal decision trees with non-binary features. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Schloss Mngsuubl-Lcibniiz-Zenturr für Informatik, 2021.
Mingfei Shi, Kaixun Hua, Jiayang Ren, and Yankai Cao. Global optimization of k-center clustering. In International Conference on Machine Learning, pages 19956-19966, PMLR, 2022.
Sicco Verwer and Yingqian Zhang. Learning decision trees with flexible constraints and objectives using integer optimization. In International Conference on Al and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pages 94 103. Springer, 2017.
Sicco Verwer and Yinggian Zhang. Learning optimal classification trees using binary linear program formulation. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 1625-1632, 2019.
Haoran Zhu, Pavankumar Murali, Dzung Phan, Lam Nguyen, and Jayant Kalagnanam. A scalable mip-based method for learning optimal multivariate decision trees. Advances in Neural Information Processing Systems, 33:1771-1781, 2020.
Yong Zhuang, Matthew Almeida, Melissa Morabito, and Wei Ding. Crime hot spot forecasting: recurrent model with spatial and temporal information. In 2017 IEEE International Conference on Big Knowledge (ICBK), pages 143-150. IEEE, 2017.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See section
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work focus on developing novel training method on optimal decision tree
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] all proof' are in appendix file from the supplementary materials
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 5
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A] Since our algorithm is a deterministic global optimization algorithm, whatever random seed provide, the algorithm will always converge the
same global optimum (with given optimality gap)
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 3
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] OCT is coded by ourselves and the code is provided in the supplementary materials and we also provide the result reported in their original paper for reference.
12

---

(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material or as URL? [Yes]
(d) Did you discuss whether and how consent
obtained from people whose data you'le rou're using/curating? [N/A] We are using data from UCI Machine Learning Repository (e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A] We are using data from UCI Machine Learning Repository
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] Our work didn't use crowdsourcing conducted research with human subjects
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals. if applicable? [N/A] Our work didn't use crowdsourcing or conducted research with human subjects
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] Our work didn't 't use crowdsourcing or conducted research with human subjects
13


Reviews:
[{"review_id": "_7lOIsqP8r1", "reviewer": "Reviewer_fTBj", "summary": "The paper presents a new approach for globally optimal decision trees. Inspired by the scalability issues of previous work, the paper proposes to formulate the problem as a two-stage optimization problem and develop a specialized branch and bound approach for training optimal decision trees for classification problems. The approach uses decomposition of bound computation that can be parallelized as well as a sample reduction technique. Experiments show the approach outperforms the well-known OCT approach and the heuristic algorithm CART.\n\n\n-----\nI thank the authors for their thoughtful response and their attempt to address the comments. Although the new results do not cover most of the approaches I suggested, I acknowledge it may be challenging to obtain and run the code in short time. It would be useful to add at least some of them once you successfully run them.\n\nAlso, the results for depth of 3 are promising and show the proposed approach outperforms the baselines.\n\nI have therefore increased my score.", "questions": "I don't have any questions beyond my points above", "limitations": "I did not identify any issues related to limitations and potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Interesting and novel approach for globally optimal decision trees based on two-stage optimization and specialized branch and bound algorithm.\n- Strong theoretical guarantees and focus on both quality solution and the optimality gap.\n- Experiments show the approach significantly outperforms the baselines.\n\nWeaknesses:\n- Missing important baselines in experiments: current experiments only compare to OCT and ignore a large amount of approaches for optimal decision trees developed over the last year. In particular, despite the focus on MIP and continuous features, the work should compare against prominent non-MIP-based optimal approaches and approaches that first convert continuous values to discrete values using a transformation that maintains optimality (e.g., assigning a single variable to each value). Some examples include [1-5] listed below.\n- Experiments are limited to trees of depth 2. This is a very shallow depth and many previous works have considered deeper trees.\n- Ablation study: the paper would benefit from an analysis of the impact of different components (e.g., performance without the sample reduction technique).\n- Minor points:\n\t* line 3, 36: \"tailed\" I think should be \"tailored\"?\n\t* line 104: \"feature size\" -> \"number of features\"?\n\t* line 214: \"reduce\" -> \"reduces\"\n\n[1] Verwer, Sicco, and Yingqian Zhang. \"Learning optimal classification trees using a binary linear program formulation.\" Proceedings of the AAAI conference on artificial intelligence. Vol. 33. No. 01. 2019.\n[2] Aghaei, Sina, Andrés Gómez, and Phebe Vayanos. \"Strong optimal classification trees.\" arXiv preprint arXiv:2103.15965 (2021).\n[3] Aglin, Gaël, Siegfried Nijssen, and Pierre Schaus. \"Learning optimal decision trees using caching branch-and-bound search.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 04. 2020.\n[4] Hu, Hao, et al. \"Learning optimal decision trees with maxsat and its integration in adaboost.\" IJCAI-PRICAI 2020, 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence. 2020.\n[5] Shati, Pouya, Eldan Cohen, and Sheila McIlraith. \"SAT-based approach for learning optimal decision trees with non-binary features.\" 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Y96XV5ceg1I", "reviewer": "Reviewer_gshW", "summary": "The authors propose an approach for finding exactly optimal decision trees using a two stage stochastic program, with the first stage problem consisting of the variables related to the structure of the tree such as splits, and the second stage variables consisting of example-related terms such as what leaves the sample falls into as it progresses in the tree structure. The approach uses a modified branch and bound approach to solve this two-stage problem and demonstrates improved runtime performance and testing accuracy over baselines in larger datasets which are either heuristic decision tree methods or optimal decision trees which are formulated as large mixed integer programs. ", "questions": "Can individual components of the proposed approach be integrated into previous work on optimal classification trees?\n\nDoes the proposed approach close the gap faster in terms of runtime? What does the gap convergence here look like compared to previous approaches? It would be helpful to give an idea of what this looks like throughout the solving process to understand how beneficial/harmful it would be to stop the solving procedure early given time constraints.\n\nIs it possible to compute the gap for the CART models? Here you still have the quality of the primal solution and you might use one of the computed bounds to determine how suboptimal the CART solution is.\n\nIs it possible to encode rules enforcing fairness into the solving procedure? Is the formulation flexible enough to address other objectives in the training procedure?\n\nSmall changes:\nLine 50: handle large dataset[s]\n", "limitations": "The authors adequately address the limitation of only being able to solve for trees with limited depth as previous work is also limited by this constraint. It is a promising direction for future work but scalability here is one main limitation of the current work in optimal decision trees. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall the paper’s main strength is making the guarantees of optimal decision trees applicable for larger datasets by proposing an intricate solving approach that enables efficient closing of the primal and dual bound. Furthermore, it Is able to demonstrate the benefit of having optimal classification trees by finding improved solutions that outperform standard methods in terms of test time performance. The proposed approach not only gives improved primal solutions in the case of large datasets, but also gives performance bounds for the dataset it is trained on and is able to determine how suboptimal the current solution can possibly be.\n\nThe paper itself is clear and well-written, adequately explaining the approaches in previous work and the significance with respect to the previous work. Furthermore, the solution algorithm is original and the different components seem to be well-founded in addressing limitations of previous work.\n\nThe proposed approach has several components that tackle different challenges of the optimal decision tree problem. It would strengthen the paper to display results corresponding to the strengths of the work to validate the approach. Specifically, it would be interesting to see the gap convergence plots for the given approach and potentially a baseline to show that the work done for improving the bound does indeed result in tighter bounds and better gap closure. Additionally, it would be interesting to see if these types of approaches could be integrated into previous work to understand the importance of the individual contributions.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Odwws8g_fG4", "reviewer": "Reviewer_v4RW", "summary": "This paper presents an algorithm for learning the optimal decision tree w.r.t. regularized training loss. The algorithm is based on the branch-and-bound method, and takes a two-stage stochastic optimization approach to decompose the problem. The main novelty of the algorithm is the computation of the dual bound at each search node, where the authors: use separability to split the second stage problem into many \"group\" problems solved in parallel, and introduce a data reduction scheme to further reduce the node problem sizes. The authors present a computational study comparing their method against existing methods for training tree models in terms of model accuracy, optimality gap, and solve time. ", "questions": "* The typesetting of (2) appears pretty broken: Missing \"for all\" quantifiers, (2m) does not seem to make sense as s is not a decision variable, etc.\n* Please situate (2) in the literature: Is this equivalent to the formulation of Bertsimas and Dunn, or are their modifications for which you are claiming novelty? If so, please highlight those modifications and, importantly, provide a formal proof of the validity of the formulation in the appendix.\n* \"BB node\" is used in the abstract and introduction, but is only defined at the end of the introduction.\n* The alpha symbol is reused with different meanings in (1) and Section 3.\n* I believe you want to flip the min and sum in (6) and (8).", "limitations": "The authors do not explicitly address the potential negative social impact of their work. The discussion of limitations is terse, but sufficient.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is situated in an area of interest and significance to the NeurIPS community, and presents algorithmic improvements that are, to my knowledge, original. The computational results suggest an improvement over the state of the art, in terms of model accuracy and scalability of the training algorithm. The paper is somewhat difficult to read at points, and does not do as much to contextualize the results with the existing literature as it could.\n\nMy main concern with the paper is the hyperparameter selection in the computational study. The authors select a single regularization parameter value alpha for the entire study, seemingly arbitrarily. This regularization parameter can have a substantial impact on the model accuracy, as well as potentially on the solve time. It is not obvious to me that choosing the same value for the different algorithms is the \"right\" thing to do in order to get the highest quality models. It is certainly not the case that this value should remain fixed for different data sets, as the authors acknowledge on page 9.\n\nTherefore, I think the computational study would be much stronger the regularization hyperparameter is selected through validation, done separately for each of the three methods and each of the data sets.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-RF0BucWuKR", "reviewer": "Reviewer_25Mp", "summary": "The paper proposes a branch-and-bound based approach to obtaining the optimal decision tree. The basic idea is to separate the problem into two stages, the first of which is about structure of tree and the second of which is about variables that specifies the allocation and cost of samples. ", "questions": "In (6) and (10), 'min' should be the inside of \\sum? Although the subscript 's' is in the sum index, it is also shown outside of the sum (m_s). \n\nIn Algorithm 1, what does 'j \\in {1,2} is infeasible' mean?", "limitations": "A limitation about the tree depth is described in Section 6.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The basic idea would be reasonable and the empirical results suggest efficiency of the proposed method.\n\n- In abstract: \n\n> find global optimal solutions with a small optimality gap for datasets with over 245,000 samples.\n\nI feel that this statement is seemingly a bit exaggerated too much because the result is obtained by 1000 cores (though in the introduction, it is described). \n\n- If I correctly understand, the entire general framework (two stage decomposition with branch-and-bound) has been already studies in Cao and Zavala 2019, and Hua et al., 2021. There exist technical differences, but the basic idea of the bound and the algorithm was already established. Although the authors explain it mainly in Introduction, the fact that the proposed method is based on those past work is not fully clear from the descriptions in the paper. \n\n- The variables in (3) are not defined in the main text.\n\n- A (minor) weak point of the paper would be its complexity of the technical writing. Because of the large number of variables and complicated definition of the optimization problem, the paper is a bit difficult to follow. More detailed explanations particularly for the problem (2) would help readers even if it is only in appendix (Actually, I had to check Bertsimas and Dunn 2017 to understand the basic formulation of (2)).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept