Learning Binary Trees via Sparse Relaxation
Authors: Valentina Zantedeschi
Matt Kusner
Vlad Niculae
Venue:  (2021)
Keywords: optimization
binary trees

Abstract: One of the most classical problems in machine learning is how to learn binary trees that split data into meaningful partitions. From classification/regression via decision trees to hierarchical clustering, binary trees are useful because they (a) are often easy to visualize; (b) make computationally-efficient predictions; and (c) allow for flexible partitioning. Because of this there has been extensive research on how to learn such trees. Optimization generally falls into one of three categories: 1. greedy node-by-node optimization; 2. probabilistic relaxations for differentiability; 3. mixed-integer programming (MIP). Each of these have downsides: greedy can myopically choose poor splits, probabilistic relaxations do not have principled ways to prune trees, MIP methods can be slow on large problems and may not generalize. In this work we derive a novel sparse relaxation for binary tree learning. By sparsely relaxing a new MIP, our approach is able to learn tree splits and tree pruning using state-of-the-art gradient-based approaches. We demonstrate how our approach is easily visualizable, is efficient, and is competitive with current work in classification/regression and hierarchical clustering.

Under review as a conference paper at ICLR 2021
LEARNING BINARY TREES VIA SPARSE RELAXATION
Anonymous authors Paper under double-blind review
ABSTRACT
One of the most classical problems in machine learning is how to learn binary trees that split data into useful partitions. From classffiaation/egressin via decision trees to hierarchical clustering. binary trees are useful because they (a) are often easy to visualize; (b) make computationally-effiiiii
predictions; and (c) allow for flexible partitioning. Because of this there has been extensive research on how to learn such trees that generally fall into one of three categories: 1. greedy node-by-node optimization; 2. probabilistic relaxations for differentiability; 3. mixed-integer programs (MIP). Each of these have downsides: greedy can myopically choose poor splits, probabilistic relaxations do not have principled ways to prune trees, be slow on large problems and may not generalize. In this work we derive novel sparse relaxation for binary tree learning. By deriving new MIP and sparsely relaxing it, our approach is able to learn tree splits and tree pruning using argmin differentiation. We demonstrate how our approach is easily visualizable and is competitive with current tree-based approaches classification/regresioon and hierarchical clustering.
MIP methods
INTRODUCTION
Learning discrete structures from unstructured data is extremely useful for a wide variety of real-world problems (Gilmer et al., 2017 7 Kool et al., 2018 Yang et al., 2018). One of the most computationally- efficient, vasily-visualizable discrete structures that are able to represent complex functions are binary trees. For this reason, there has been a massive research effort on how to learn such binary trees since the early days of machine learning (Payne & Meisel 1977 Breiman al. 1984 [ennett 1992] Bennett & Blue 1996). Learning binary trees has historically been done in one of three ways. The first is via greedy optimization, which includes popular decision -ree methods such classification and regression trees (CART) (Breiman et al.) 1984) and ID3 trees (Quinlan 1986), among many others. These methods optimize a splitting criterion for each tree node, based on the data routed to it. The second set of approaches are based on probabilistic relaxations (Irsoy et al. 2012 Yang al. 2018). The idea is to optimize all splitting parameters at once via gradient-base methods, by relaxing hard branching decisions into branching probabilities. The third approach optimizes trees using mathematical programming (MIP) (Bennet 1992. Bennett & Blue 1996). This jointly optimizes all continuous and discrete parameters to find globally opotimall trees
Each of these approaches have clear shortcomings. First, greedy optimization is clearly suboptimal: tree splitting criteria are even intentionally crafted to be different than the global tree loss, as the global loss does not encourage tree growth (Breiman et al., 1984). Second, probabilistic relaxations: (a) are rarely sparse, so inputs probabilistically contribute to branches they would never visit if splits are mapped to hard decisions; (b) they do not have principled ways to prune trees, as the distribution over pruned trees is often intractable. Third, MIP approaches, while optimal, are only computationally tractable on training datasets with thousands of inputs (Bertsimas & Dunn 2017). and do not have well-understoon oft-ol-sample generalization guarantees.
In this paper we present a new approach to binary tree learning based on sparse relaxation and argmin differentiation. Our main insight is that by quadratically relaxing an MIP that learns the discrete parameters of the tree (input traversal and node pruning), we can differentiate through it to simultaneously learn the continuous parameters of splitting decisions. This allows to leverage the superior generalization capabilities of stochastic gradient optimization to learn splits, and gives
Herr we focus learning single trees instead of tree ensembles; work easily extends to ensembles.

---

Under review as a conference paper at ICLR 2021
derive customized algorithms to compute the forward and backward passes through this program that are much more efficient than generic approaches (Amos & Kolter 2017). We demonstrate that (a) in classficcatinn/eerrsssn method, which learns a single tree and a classifier on top of it, is competitive with greedy, probabilistie, MIP-hased tree methods, and even powerful ensemble methods; (b) in hierarchical clustering match or improve upon the state-of-the-a
principled approach learning tree pruning. Further,
RELATED WORK
The paradigm of binary tree learning has the goal of finding a tree that iteratively splits data into meaningful, informative subgroups, guided by some criterion. Binary tree learning appears in wide variety of problem settings across machine learning. We briefly review work in two learning settings where latent tree learning plays key role: 1. Classifcation/Regresssii clustering. Due to the generality of our setup (tree learning with arbitrary split functions, pruning, and downstream objective), our approach can be used learn trees in any of these settings. Finally, we detail how parts of our algorithm are inspired by recent work in isotonic regression.
and 2. Hierarchical
Decision trees for classification and regression have a storied history, with early popular methods that include classification and regression trees (CART; Breiman et al., 1984). ID3 (Quinlan, [986), and C4.5 (Quinlan 1993). While powerful, these methods are greedy: they sequentially identity 'best' splits as those which optimize a split-specific score (often differ- ent from the global objective). As such, learned trees are likely sub-optimal for the classifica- tion/regression task at hand. To address this, Carreira-Perpinán & Tavallali (2018) proposes an alternating algorithm for refining the structure and decisions of tree so that it smaller and with reduced error, however still sub-optimal, Another approach is to probabilisticaly relax the discrete splitting decisions of the tree IIsoy et al. 2012 Yang et al. 2018 Tanno et al., 2019). This allows the (relaxed) tree to be optimized w.r.f. the overall objective using gradient- techniques, with known generalization benefits (Hardt et al. 2016 Hoffer et al. 2017). Variations on this approach aim at learning tree ensembles termed "decision forests' (Kontschieder et al. 2015 Lay et al. 2018 Popoy ict al., 2019). The downside of the probabilistic relaxation approach is that there is no principled way to prune these trees as inputs pass through all nodes of the tree with some probability. A recent line of work has explored mixed-integer program (MIP) formulations for learning decision trees. Motivated by the billion factor speed-up in MIP in the last 25 years, |Rdiin & Ertekin (2018) proposed mathematical programming approach for learning provably optimal decision lists (one-sided decision trees: rrees:Letham al. 2015). This resulted in line of recent follow-up works extending the problem to binary decision trees (Hu et al. 2019; Lin et al.
Classffication/Regresssic
2020) by adapting the efficient discrete optimization
algorithm (CORELS; Angelino et al. (2017). Related to this line of research, [Bertsimas & Dunn Angelino
2018 Aghaci et al.) 2019; Verwer & Zhang [2019] Aghaei et al., 2020) phrased the objective of CART as an MIP that could be solved exactly. Even given this consistent speed-up all these methods are only practical on datasets with at most thousands of inputs (Bertsimas & Dunn (017)) and with non-continuous features. Further, the oft-of-sample
(2017) and its follow-up works Güülük et al.
generalizability of these approaches is not well-studied, unlike stochastic gradient descent learning.
Hierarchical clustering. Compared to standard flat clustering, hierarchical clustering provides a structured organization of unlabeled data in the form of a tree. To learn such a clustering the vast majority of methods are greedy and work in one of two ways: 1. Agglomerative:
'bottom-up' approach that starts each input in its own cluster and iteratively merges clusters; and 2. Divisive: a 'top-down' approach that starts with one cluster and recusively splits clusters (Zhang et al. 1997,
Widyantoro et al. 2002, Krishnamurthy et al. 2012 Dasgupta 2016 Kobren et al.] 2017] Moseley Wang 2017). These methods suffer from similar issues as do greedy approaches to tree learning for classification/reeressooo they may be sub-optimal for optimizing the overall tree. Further they are often cmmputationally-xxeemi classfication/eegrssioon recent work has designed probabilistic relaxations for learning hierarchical clusterings via gradient-bar based methods (Monath et al. 2019).
due to their sequential nature. Inspired by approaches for
Our work takes inspiration from both the MIP-based and gradient-basee approaches. Specifically, frame learning the discrete tree parameters as an MIP, which we sparsely relax to allow continuous parameters to be optimized by argmin differentiation methods.
2

---

Under review as a conference paper at ICLR 2021
Argmin differentiation. Solving an optimization problem differentiable module within parent problem tackled with gradient-based optimization methods is known as argmin differentiation, particular instance of bi-level optimization (Gould et al. 2016). This situation arises in as diverse scenarios as hyperparameter optimization (Pedregosa, 2016). meta-learning (Rajeswaran et al.
2019), or structured prediction (Stoyanov et al. 2011 Domke 2013 Niculae et al. 2018). General algorithms for quadratic Amos & Kolter (2017) and disciplined convex programming (Section 7, Amos 2019; Agrawal et al., 2019a have been given, well as expressions for more specific
cases like isotonic regression (Djolonga & Krause, 2017). By taking advantage of the very specific structure of the decision tree induction problem, we obtain direct, efficient algorithm.
Isotonic regression. Also called monotonic regression, isotonic regression (Barlow et al., 1972) constrains the regression function to be son-derreasingnno- srreaaiinnnnonn-ncrrsiingggg This is useful if one has prior knowledge of such monotonicity (e.g., the mean temperature of the climate is non-decreasing). classic algorithm is points that violate the monotonicity constraint (Barlow et al. 1972). This initial algorithm has been generalized and incorporated into convex programming frameworks (see Mair et al. (2009) for an excellent summary of the history of isotonic regression and its extensions). Our work builds off of the generalized PAV (GPAV) algorithm of Yu & Xing (2016).
adjacent-violators (PAV), which optimizes the pooling of adjacent
METHOD
Given inputs {x; /i= 1, our goal is to learn latent binary decision tree T with maximum depth D. This tree sends each input through branching nodes to a specific leaf node in the tree. Specifically, all branching nodes Ta C T split input by forcing it to go to its left child if so(x) < 0, and right otherwise. There are three key parts of the tree that need to identified: 1. The continuous parameters 0g E Rd that describe how 89, splits inputs at every node (; 2. The discrete paths z made by each input x through the tree; 3. The discrete choice a of whether a node should be active or pruned. We describe how to learn each of these below.
3.1 CREE-TRAVERSAL & PRUNING PROGRAMS
Imagine the splitting functions of the tree so, are fixed. Given this, the following integer linear program (ILP) describes how inputs x traverse the tree. The solution žµt E {0, 1} indicates x; reaches node E T (for notational simplicity let 2, E {0, 13177 be the vectorized indicator for x;),
max
Σ 1=1
(1)
s.t. Vi E [n],
Gie = min (rat, Lit
Ta = min (x,), Vt' E (nt)).} La = min (-ss (xx), Vt' E Az))))
2/ E 1).
Here (t) (t) is the set of ancestors of node i. whose left child must be followed to get to f, and similarly for At) The quantities qu (where q: E RIT| is the tree-vectorized version of qu) describe the 'reward' of sending x; to node l. This is based on how well the splitting functions leading to / are satisfied (ga is positive if all splitting functions are satisfied and negative otherwise).
Notice that the solution unique so long as 89, (x:) for all E T, E .I....,n) (i.e., 80, (x;) =0 means there is no preference to split x; left right). Further note that the integer constraint &ir can be relaxed to an interval constraint 2it E [0, 1] without loss of generality. This because so, (x;) + 0 then 2 0 if and only if g: and 2 1 when q:
(and q: + 0).
While the above program works for any fixed tree, we would like to be able to also learn the structure of the tree itself. Let 77, E IR be our preference for pruning/keeping node t (larger n7 indicates node t should be kept). To encourage this pruning preference while ensuring connectivity, we introduce an additional optimization variable a, E {0, 1), indicating if node i T is active (if or pruned (if 0).
3

---

Under review as a conference paper at ICLR 2021
We may now adapt eq. into the following pruning-award mixed integer program (MIP):
T Z qi
=
max Bi 2
i=1
s.t. Vi E
S Opt))
4t E ET (root)
z S
Za E [0, 11, ae {0,1}.
Here we have removed the first three constraints in eq. as they are a deterministic computation independent of 21,...; :.n a. Further p(t) indicates the parent of node The added constraint az I dp(t) ensures that child nodes f are pruned parent nodes p(t) are pruned. While the new constraint Ziz Gr ensures that no point x; can reach node if node is pruned
3.2 LEARNING TREE PARAMETERS
A natural approach to learn splitting parameters 0, would be to do so in the MIP itself, as in the optimal tree literature. However, this would severely restrict allowed splitting functions as even linear splitting functions can only practically run on at most thousands of training inputs (Bertsimas & Dunn 2017). Instead, we propose to learn 59, via gradient descent. To do so, we must be able to compute gradients 8m and th However, the solutions of eq. are discontinuous and piecewise-constant "q
To solve this, we relax the integer constraint on a to the interval [0, 1] and add quadratic regularization 1/2 E, lz 112 + 1/2||a1/2 Rearranging and negating the objective yields
T (q qn) arg min
1/2
2i qill 1/2117 all2
(3)
21....
s.t. Vi [n], at S ap(t),
Vt E ET) (root)
Za at
E [0, 1]. az E [0,
The regularization makes the objective strongly convex, from convex duality it follows that T, is Lipschitz continuous (Zalinescu 2002, Corollary 31). By Rademacher's theorem (Borwein & Lewis 2010 Theorem 9.1.2), T , is thus differentiable almost everywhere. Generie methods such as OptNet (Amos & Kolter 2017) could be used to compute the solution and the gradients. However, by next derive efficient specialized algorithm. The main
using the tree structure of the constraints, insight, shown below, reframes pruned binary tree learning as isotonic optimization.
Proposition 1. Ler C = {a E RI.. a I apttt) for all E T {roor}}- Consider
a" = arg min aECT(o.11IT)
- 110)
Σ
1/2(a; - qit)
(4)
BET
i:a Sqit
Define [2"] = (9))). Then, TqI qn) zi 2, a"
Proof.
The constraints and objective function of eq. Jar separable, so we may push the minimization w.t.t z inside the objective, resulting in:
arg min aecn(o.
1/2/1m all2 +
min 1/2(2u - qit)²
(5)
05 Sec
1ET
Each of the inner nested minimizations, mings= Sa. 1/2(zu )a)² 2 is a one-dimensional projection onto box constraints, with solution = Projpp,ad (1t)). We may use this result to eliminate from objective, noting that
1/2 lio
qa 0
1/2(2 qa)²
0,
qu < az
(6)
1/2(a+ q
2 0t
Here Projg(#) is the projection of set S. I are box constraints, projection amounts clipping.
4

---

Under review as a conference paper at ICLR 2021
Algorithm Latent decision tree induction via isotonic optimization.
I: initial partition (2), 2
2: for all G E do 3: dg arg min, Ee 9c(a)
Proposition 2
4: while exists such that a; > Op(()
fmax + arg max, (ar az > (p(t)}
6: merge G +- G CUC where E G and p(t) E G".
7: update ag + arg min, 9cla)
Proposition again
the first conditions are constants w.r.t. a, Thus, the objective functions eq. L and eq. differ by a constant. As their constraints are also the same, they have equivalent minimizers a*.
Efficiently inducing trees as isotonic optimization. From Proposition notice that eq. is an instance of tree-structured isotonic optimization: the objective decomposes over nodes, and inequality constraints correspond to edges in rooted tree:
arg min Eg((at) aEC
where (ax)) = 1/2(a; - me) +
Σ d:c Sqit
1/2(0x - q=0)² (o.1)(ar)-
(7)
IET
where of a [0 and otherwise. This problem can be solved by generalized pool adjacent violators (PAV) algorithm: Obtain tentative solution by ignoring the constraints, then iteratively remove violating edges at > ap(t) by pooling together the nodes at the end points. At the optimum, the nodes are organized into partition C 2 such that two nodes f, are in the same group G' G, then a, =a-- ag-
When the inequality constraints are the edges rooted tree, as is the case here, the PAV algorithm finds the optimal solution in at most [T| steps, where each involves updating the ag value for newly-pooled group by solving a one-dimensional subproblem of the form (Yu & Xing 2016
ag arg min Σ Eg((a).
(8)
resulting Algorithm| [ Appendix A.I gives exact and efficient solution, with algorithm that requires finding the nodes with highest qse (i.e., the nodes where x; is most highly encouraged to traverse).
It remains to show how to solve eq, The next result, proved in
Proposition The solution to the one-dimensional problem in eq. (8 for any Gs given by
Σ (a) = Proojo.j (a(k*)) where a(k") = Eleo qt E(.DESS lit
arg min
|G| +
aER LEG
x G into the highest values of q. i.e., Qym 9ymz) ... qjim), and k* is the smallest k satisfying a(k) qaa++)>
S(k) = (j()), ...., (()), is the set of indices (i,
Figure 2 shows the speed of specialized algorithm compared leading generic optimizer (details in Appendix A.2)
Backward pass and efficient implementation details. Algorithm is sequence differentiable operations that can be implemented as is in automatic differentiation frameworks. However, because of the prominent loops and indexing operations, we opt for low-level implementation as C++ only need to sort them once as preprocessing.
extension. Since the values are constant w.r.f. For the backward pass, rather than relying on automatic differentiation, we make two remarks about the form of a. Firstly, its elements organized in groups, i.e., d; af ag for (t,t') C G. Secondly, the value ag inside each group depends only on the optimal support set St S(k*) as
CCompared to Yu & Xing (2016), tree inequalities are in the opposite direction. This is equivalent to sign flip of parameter a, f.e. selecting the maximum violator rather than the minimum each iteration.
5

---

Under review as a conference paper at ICLR 2021
Algorithm 2 Learning with latent decision tree representations.
1: initialize neural network parameters Φb 0
2: initialize pruning scores 7 ~ (1(11,11))
repeat
sample batch {x.
5: induce traversals (zi Tn (x)00))))
algorithm
differentiable
6: update parameters using (to.n.o) Allvalee
autograd
defined for each subproblem by Proposition Therefore, in the forward pass, we must store only the node-to-group mappings and the sets Sg. Then, if G' is the group of node
0o7 One
< at and G. dag
0 0<ap at < 1, and (i,t') E Sa.
G 0,
otherwise.
0,
otherwise.
As T, is differentiable almost everywhere, these expressions yield the unique Jacobian at all but measure-zero set of points, where they yield one of the Clarke generalized Jacobians (Clarke) 1990).
We then rely on automatic differentiation to propagate gradients from q to the split parameters 0; since q is defined elementwise via min functions, the gradient propagates through the minimizing path, by Danskin's theorem (Proposition B.25, |ertsekas [999 Danskin 1966).
3.3 THE OVERALL OBJECTIVE
We are now able describe the overall optimization procedure that simultaneously learns tree parameters: (a) input traversals Zi...., Zn (b) tree pruning a; and (c) split parameters 0,. Given this tree, will additionally learn function fz(z,x) x) minimize arbitrary loss ((-) as follows.
E (x((((x.22)) + Al|n|le 0.
min
(10)
where 21 Zn a: T .0 (xx)).
In practice, we perform mini-bate batch updates for efficient training; the procedure is sketched in Algorithm 2 Recall (-)()) is the solution to the tree program (), so we may update the parameters 17 and 0 by prok-propagation. Here we define gx(x;) == qi make explicit the dependence of q, The regularization | llQ can be any norm (in practice we find = oc to perform the best.) The overall model is represented in Figure T
4 EXPERIMENTS
In this section showcase method both: (a) Classifica- tion/Regression for tabular data, where tree-based models have been demonstrated to have superior performance over MLPs (Popov al. 2019); and (b) Hierarchical clustering on unsupervised data. Our experiments demonstrate that method leads to predictors that competitive with state-of-the-art tree-based approaches. Further we visualize the trees learned by our method, and how sparsity easily adjusted by tuning the regularization parameter A.
x
Tv, (x)))
(x. x)
Architecture details. We use linear function or multi-layer perceptron (L fully-connected layers with Elu activation (Clevert al. 2015) and dropout) for (o(-) and choose between linear or linear followed by Elu splitting
Figure Model overview.
functions s-(-) (we limit the search for simplicity, there are no restrictions except differentiabillty).
4.1 SUPERVISED LEARNING ON TABULAR DATASETS
Our first set of experiments is on supervised learning with heterogeneous tabular datasets, where we consider both regression and binary classification tasks. We minimize the Mean Square Error (MSE)

---

Under review as a conference paper at ICLR 2021
Table 1: Results tabular datasets. We report average and standard deviations over runs of MSE for regression datasets: Year, Microsoft and Yahoo, and error rate for classification datasets: Click and Higgs. Best result, and those within a standard deviation from it, for each family of algorithmss (single tree or ensemble) are in bold. Dashes "-' indicate that the method cannot be run (i.c.. a method is designed only for classification). Experiments are run on machine with 16 CPUs and 63GB of RAM, with training time limit of 3 days. We denote methods that exceed this memory and training time as OOM and OOT, respectively.
method
YEAR
MICROSOFT
YAHOO
CLICK
HIGGS 0.3220 E 1e-3
CART
1.34
0.6914 I 3e-3
0.6190 3e.3
0.3780 6e-3
Single Tree
DNDT
0.4866 le-2
00M
OPTREE
0.4100 4e-2
OOT
NDF-1
0.3344 + 5e-4
0.2644 = 8c-4
ANT
77.84
0.5721 + 17c-4
0.5893 + 22c-4
Ours
77.11 + 0.21
0.5728 + 4e-1
0.5911 + 5e-4
0.3342 + 4c-4
0.2227 + 6c-4
Ens.
NODE
76.21 - 0.12
0.5570 = 2e-4
0.5692 2e-4
0.3312 + 2e-3
0.2101 + 5e-4
XGBoost
78.53 4: 0.09
0.5544 1e-4
0.5420 + 4e-4
0.3310 + 2e-3
0.2328 + 3e-4
on regression datasets and the Binary Cross-Entrope (BCE) on classification datasets. We compare our results with tree-based architectures, which either train a single or an ensemble of decision trees. Namely, we compare the greedy classification and regression trees (CART) (Breiman
iet al. [1944) and to the optimal decision tree learner with local search (Optree-LS: Dunn 2018). We
also consider three baselines with probabilistic routing: deep neural decision trees (DNDT: Yang
iet al. 2018), deep neural decision forests (Kontschieder et al. 2015) configured to use an ensemble size of I (NDF-1) and adaptive neural networks (ANT:TTanmo et al. 2019). As for the ensemble baselines, we compare to NODE (Popov et al. 2019), the state-of-the art method for training forest of differentiable oblivious decision trees on tabular data, and to XGBoost (Chen & Guestrin 2016), a scalable tree boosting method. We carry out the experiments on the following datasets. Regression: Year Maatiu- et al.) 201T). Temporal regression task constructed from the Million Song Dataset; Microsoft (Qin & Liu 2013),, Regression approach to the MSLR- -eeb- Query-URe relevance prediction for learning to rank; Yahoo (Chapelle & Chang, 201T), Regression approach to the C14 learning-to-rank challenge. Binary classification: Click, Link click prediction based on the
KDD Cup 2012 dataset, encoded and subsampled following Popov et al. (2019); Higgs (Baldi et al., 2014) prediction of Higgs boson-producing events.
For all tasks, we follow the preprocessing and task setup from (Popov et al. 2019). All datasets come with training/test splits. We make use of 20% of the training best model over the epochs and for tuning the hyperparameters. We tune the hyperparameters for all methods but for Optree, as its long training time makes hyper-parameter tuning unfeasible. Details are provided in the appendices. Finally, we optimize eq. (TO) and all neural network methods (DNDT, NDF, ANT and NODE) using the Quper-Hyp Adam (Ma & Yarats 2018) stochastic gradient descent method, with default parameters and batch size equal to 512. Table reports the obtained results f Unsurprisingly, ensemble methods outperfom single-tree ones on all datasets, although at the cost of being harder to visualize/interpre.. Our method has the advantage of (a) generalizing to any task; (b) outperforming or matching all single-tree methods; (c) approaching the performance of ensemble-based methods. Additional experiments reported in the appendices show that model is also significantly faster to train, compared to its differentiable tree counterparts NDF-1 and ANT, while matching beating the performance of these baselines.
validation for selecting the
Further comparison with optimal tree baselines. We run a set of experiments on small binary classification datasets to compare our method with optimal tree methods. Specifically we compare against two versions of Optree: one that solves the MIP exactly (Optree-MIP) (Bertsimas & Dunn 2017). and another that solves it with local search Optree-LS LS (Dunn) 2018). We also compare with the state-of-the-as optimal tree method of Lin et al. (2020), called GOSDT. We consider the Mushrooms binary classification dataset (Schlimmer 1987): ) prediction between edible and poisonous mushrooms, with 8124 instances and 22 features We apply stratified split on both datasets to obtain 60%-20%-00%
ceiiin-vaiiiaainnteeee sets, convert categorical features to ordinal, and z-score them. For our method, we apply the Quasi-Hyperbon Adam optimization algorithm, with batch size equal to 512. Further details about the experimental setup are available in the appendices.
*DNDT, Optree-LSS and NDF handle only classification tasks.
7

---

Under review as a conference paper at ICLR 2021
Table 2: Results on the Mushrooms tabular dataset. We report average training time (s), and average and standard deviations of test error rate over runs binary classification datasets. We bold the best result (and those whose standard deviation overlaps the mean of the best result). Experiments are run on a machine with 16 CPUs and 63GB RAM. We limit the training time to 3 days.
MUSHROOMS
method OPTREE-MIP
training time (s)
error rate
OOT
OPTREE-LS
OOT
GOSDT
214
0.0122 - 0.0027
Ours
66
0.0723 + 0.0544
CVXPy
Table 3: Results for hierarchical clustering. We report average and standard deviations of dendrogram purity over four runs. Best results and all within standard deviation from it are in bold.
13:
ours
10:
time 65)
12-
20
METHOD
GLASS
COVTYPE
10-0
107
22
10
Ours
0.494 + 0.025
0.467 1 0.006
gIIHC
0.463 0.002
0.444 1 0.005
Figure 2: Comparison of Algorithm
HKMeans
0.508 0.008
0.440 0.001
ning time (ours) with running time evxpy DDamond & 2016] et al.
BIRCH
0.429 - 0.013
0.440 0.002
2018 with the OSQP solver (Stellato et al.
2020 for tree depth D= varying
Table reports the performance of methods across 4 runs. Both OPTREE variants do not finish in under days. On Mushrooms our method runs 3 times faster than GOSDT at the expense of higher error. We believe the slow scaling GOSDT due to the fact that it binarizes features, working with 118 final binary attributes Mushrooms.
4.2 SULE-IUPERVISED HIERARCHICAL CLUSTERING
To show the versatility of our method, we carry out a second set of experiments on hierarchical clustering tasks. Inspired by the recent success of self-supervised learning approaches (Lan et al.. 2019 He et al. 2020). we learn tree for hierarchical clustering in a self-supervised way. Specifically. we regress subset of input features from the remaining features, minimizing the MSE. This allows us to use eq. (T)) to learn hierarchy (tree). To evaluate the quality of the learned trees, we compute their dendrogram purity (DP; Monath et al. 2019). DP measures the ability of the Iearned tree to separate points from different classes, and corresponds to the expected purity of the least common ancestors points of the same class.
We experiment the following datasets: Glass (Dua & Grafi 2017); glass identification for forensics, and Covtype (Blackard & Dean 1999, Dua & Graff 2017): cartographic variables for forest cover type identification. For Glass, regress features 'Refractive Index' and 'Sodium." and for Covtype the horizontal and vertical DDsstance To Hydrology.' We split the datasets into training/validationnnest sets, with sizes 60%/20%//0% Here we only consider linear fa- As before, optimize Problem T0 using the Glass, and tune the hyper-parameters using the validation set.
Adam algorithm, with batch size equal to 512 for Covtype and 8 for
As baselines, we consider: BIRCH (Zhang et al. 1996) and Hierarchical KMeans (HKMeans), the standard methods for performing clustering on large datasets; and the recently proposed gradient- based Hyperbolic Hierarchical Clustering (gHHC) (Monath et al.) (219)) designed to construct trees in hyperbolic space. Table @ablerrreport reports the dendrogram purity scores for all methods. Our method matches or outperforms all methods, even though not specifically tailored to hierarchical clustering.
Tree Pruning The ayper-parameter À in eq. 10 controls how aggressively the tree is pruned, hence the amount of tree splits that actually used to make decisions. This is a fundamental feature of our framework as it allows to smoothly trim the portions of the tree that are not necessary for the downstream task, resulting in lower computing and memory demands at inference. In Figure 3
8

---

Under review as a conference paper at ICLR 2021
DP 0.4215; EN
DP 0.3847; EN 12
DP O. 0.3971; EN 17
Le
Figure Glass tree routing distribution, in rounded percent of dataset, for left-to-right (0, 0.001, 0.13.
The larger X, the more nodes are pruned. We report dendrogram purity (DP) and total empty nodes (EN).
(a) Window-Float-oo Float-Build (b) Window-Flood Float-Vehicle
(c) WoContnnsss
(d) NonW WeHeedlamssss
Figure 4:
Class routing distributions on Glass, with distributions normalized over each depth level. Trees were trained with optimal hyper-parameters, (depth 6=)),, but we plot nodes up to D= 4 for visualization ease.
study the effects of pruning on the tree learned on Glass with depth fixed to D We report how inputs are distributed over the learned tree for different values of We notice that the number of empty nodes, i.e., nodes that not traversed by any data point, increases together with À up to certain value in order not to significantly deteriorate results (as measured by dendrogram purity).
Class Routing In order to gain insights on the latent structure learned by our method, we study how points routed through the tree, depending their class. The Glass dataset is particularly interesting to analyze as its classes come with an intrinsic hierarchy, e.g., with superclasses Window and NonWindow. Figure 4 reports the class routes for four classes. As the trees are constructed without supervision, we do not expect the structure to exactly reflect the class partition and hierarchy, Still, we observe that points from the same class or super-class traverse the tree in a similar way. Indeed, trees for class Build [[a) and class Vehicle 4bb), which both belong to Window super-class, share similar paths, unlike the classes Containers ((c) and Headlamps ((d)
5 DISCUSSION
In this work have presented optimization approach to learn trees for variety of machine learning tasks. Our method works by sparsely relaxing a ILP for tree traversal and pruning, to enable simultaneous optimization of these parameters, alongside splitting parameters and downstream functions via argmin differentiation. Our approach nears or improves upon recent work in both supervised learning and hierarchical clustering. We believe there are many exciting avenues for future work. One particularly interesting direction would be to unify recent advances in tight relaxations of nearest neighbor classifiers with this approach learn efficient neighbor querying structures such as ball trees. Another idea is to adapt this method to learn instance-specific trees such as prrse-trees.
REFERENCES
Sina Aghaei, Mohammad Javad Azizi, and Phebe Vayanos. Learning optimal and fair decision trees for non-discriiinative decision-making, In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1418-1426, 2019.
Sina Aghaei, Andres Gomez, and Phebe Vayanos. Learning optimal classification trees: Strong max-flow formulations. arXiv preprint arXiv:2002.09143 2020.

---

Under review as a conference paper at ICLR 2021
Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. A rewriting system for convex optimization problems. Journa of Control and Decision, (11):42-60, 2018.
Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and Zico Kolter. Differentiable convex optimization layers) In Proc. of NeurlPS, 2019a.
A Akshay Agrawal, Shane Barratt, Stephen Boyd, Enzo Busseti, and Walaa M Moursi. Differentiating through a cone program Journal of Applied and Numerical Optimization, 2019(2). 2019b. doi: (123952/jamo.1.20199 archives 931
ISSN 25625527.
URL
bi piemdas..... com/
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next-generation hyperparameter optimization framework. In Proceedings of the 25rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2019.
Brandon Amos. Differentiable Optinization- Modeling for Machine Learning PhD thesis,
Carnegie Mellon University, May 2019.
Brandon Amos and Zico Kolter. OptNet: Differentiable optimization as a layer neural networks In Proc. of ICML, 2017.
Elaine Angelino, Nicholas Larus-Stone Daniel Alabi, Margo Seltzer, and Cynthia Rudin. Learning certifiably optimal rule lists for categorical data. The Journal of Machine Learning Research, 18 (1):8753-8830, 2017.
Pierre Baldi, Peter Sadowski, and Daniel Whiteson. Searching for exotic particles in high-energy physics with deep learning. Nature Communications, 5(1):1-9, 2014.
RE Barlow, DJ Bartholomev,, JM Brenner, and HD Brunk. Statistical inference under order restrictions: The theory and application of isotonic regression, 1972.
Kristin P Bennett. Decision tree construction via linear programming. Technical report, University of Wisconsin-Madison Department of Computer Sciences, 1992.
Kristin P Bennett and Jennifer A Blue. Optimal decision trees. Rensselaer Polytechnic Institute Math Report, 214:24, 1996.
Thierry Bertin-Mahieus Daniel P.W. Ellis, Brian Whitman, and Paul Lamere. The million song dataset. In Proc. of ISMIR, 2011.
Dimitri P Bertsekas. Nonlinear Programming Athena Scientific Belmont, 1999.
Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning, 106(7):1039- 1082, 2017.
Jock A Blackard and Denis J Dean. Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables. Computers and electronics in agriculture, 24(3):131-15 1999.
Jonathan Borwein and Adrian S Lewis. Convex analysis and nonlinear optimization: theory and examples Springer Science & Business Media, 2010.
Leo Breiman, Jerome Friedman, Charles J Stone, and Richard A Olshen. Classification and regression frees. CRC press, 1984.
Miguel A Carreira- Perrinaa and Pooya Tavallali. Alternating optimization of decision trees, with application to learning sparse oblique trees. In Advances in Neural Information Processing Systems, pp. 1211-1221, 2018.
Olivier Chapelle and Yi Chang- Yahoo! learning rank challenge overview. In Proceedings of the learning to rank challenge, pp. 1-24, 2011.
Tianqi Chen and Carlos Guestrin. XGBoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD '16, pp. 785-794, New York, NY, USA, 2016. ACM. ISBN 978- 42523-4-23332 doi: 10.1 215529999672.2397885 URL http::/tpo//d amm. www.oogg/..... 2et.1111//2999622221 2939778
10

---

Under review as a conference paper at ICLR 2021
Frank H Clarke. Optimization and nonsmooth analysis SIAM, 1990.
Arork-Aré Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (elus). arXiv preprint 11X.v1151..7288. 2015.
John M Danskin. The theory of max-min, with applications 14(4):641-66) 1966.
SIAM Journal on Applied Mathematics,
Sanjoy Dasgupta. A cost function for similarity-bod based hierarchical clustering. In Proceedings the forty-eighth anmual ACM symposium on Theory of Computing, pp. 118-127, 2016.
Steven Diamond and Stephen Boyd. CVXPY: Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
Josip Djolonga and Andreas Krause. NeurIPS, 2017.
Differentiable learning of submodular models In Proc. of
Justin Domke. Learning graphical model parameters with approximate marginal inference
lEEE
Transactions on Pattern Analysis and Machine Intelligence, 35(10):2454 220224444-467,, 2013.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http:://acchii//
ics. wcu.cccic edu/ml
Jack William Dunn. Optimal trees for prediction and prescription. PhD thesis, Massachusetts Institute of Technology, 2018.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In International Conference Machine Learning, pp. 1272,1272, 2017.
Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo. On differentiating parameterized argmin and argmax problems with application bivlevel optimization preprint arXiv:1607.054477, 2016. URL http:://axxiiiiii hwtp:/iwwrgggaa////// 05447
Oktay Günlük, Jayant Kalagnanam, Matt Menickelly, and Katya Scheinberg. Optimal decision trees for categorical data via integer programming. arXiv preprint arXiv: 1612.0325,, 2018.
LLC Gurobi Optimization. Gurobi refrenceeeee reference manual, 2020. URL
com
Moritz Hardt, Ben Recht, and Yoram Singer.
Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 1225-1234, 2016.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9729-9738, 2020.
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generaliza- tion gap in large batch training of neural networks. Advances in Neural Information Processing Systems, pp. 1731-1741, 2017.
Xiyang Hu, Cynthia Rudin, and Margo Seltzer. Optimal sparse decision trees. In NeurlPS, pp. 7267-7275, 2019.
Ozan Irsoy, Olcay Taner Yıldız, and Ethem Alpaydın. Soft decision trees. Proceedings of the 1 International Conference Pattern Recognition (ICPR2012), pp. 1819-1822. IEEE, 2012.
Ari Kobren, Nicholas Monath, Akshay Krishnamurthy, and Andrew McCallum. A hierarchical algo- rithm for extreme clustering. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 255-264, 2017.
Peter Kontschieder, Madalina Fiterau, Antonio Criminisi, and Samuel Rota Bulo. Deep neural decision forests. In Proceedings of the IEEE international conference on computer vision, pp. 1467-1475, 2015.
11

---

Under review as a conference paper at ICLR 2021
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2018.
Akshay Krishnamurthy, Sivaraman Balakrishnan, Min Xu, and Aarti Singh. Efficient active algorithms for hierarchical clustering. In ICML, 2012.
Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. Albert: A lite bert for self-supervised learning of language representations. In International Conference on Learning Representations, 2019.
Nathan Lay, Adam Harrison, Sharon Schreiber, Gitesh Dawer, and Adrian Barbu, Random hinge forest for differentiable learning. arXiv preprint arXiv: /802.03882, 2018.
Benjamin Letham, Cynthia Rudin, Tyler H McCormick, David Madigan, et al. Interpretable classifiers using rules and bayesian analysis: Building a better stroke prediction model. The Annals of Applied 2015.
Statistics,
Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo Seltzer. Generalized and scalable optimal sparse decision trees. In Intern, pp. Proc. of ICML, 2020.
Jerry Ma and Denis Yarats. Quasi-hyperbolic momentum and adam for deep learning. arXiv preprint 1810. 2018.
Patrick Mair, Kurt Hornik, and Jan de Leeuw. Isotone optimization in pool-adijacent-volatoor algorithm (pava) and active set methods. Journal of statistical software, 32(5):1-24, 2009.
Nicholas Monath, Manzil Zaheer, Daniel Silva, Andrew McCallum, and Amr Ahmed. Gradient- based bierarchical clustering using continuous representations of trees in hyperbolic space. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 714-722, 2019.
Benjamin Moseley and Joshua Wang. Approximation bounds for hierarchical clustering: Average linkage, bisecting k-means, and local search. In Advances in Neural Information Processing Systems, pp. 3094-3103, 2017.
Vlad Niculae, André FT Martins, Mathieu Blondel, and Claire Cardie. SparseMAP: Differentiable sparse structured inference, In Proc. of ICML. 2018
Harold J. Payne and William S. Meisel. An algorithm for constructing optimal binary decision trees. IEEE Transactions on Computers, (9):905-911) 916, 1977.
Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In Proc. of ICML., 2016.
Sergei Popov, Stanislav Morozov, and Artem Babenko. Neural oblivious decision ensembles for deep learning on tabular data. arXiv preprint arXiv:1909.06312 2019.
Tao Qin and Tie- Yan Liu. Introducing LETOR 4.0 datasets. CoRR, abs/ 306.2597, 2013. URL http::/arxiv.
J Ross Quinlan. Induction of decision trees. Machine Learning, 1(1):81-106, 1986.
J Ross Quinlan. C4. 5: Programs for machine learning. 1993.
Aravind Rajeswaran, Chelsea Finn, Sham Kakade, and Sergey Levine. Meta-learning with implicit gradients In Proc. of NeurlPS, 2019.
Cynthia Rudin and Şeyda Ertekin. Learning customized and optimized lists of rules with mathematical programming. Mathematical Programming Computation, (4):659-702, 2018.
Jeffrey C Schlimmer. Concept acquisition through representational adjustment. 1987.
Bartolomeo
Stellato, Goran Banjac, Paul Goulart, Alberto Bemporad, and Stephen Boyd. OSQP: An operator splitting solver for quadratic programs. Mathematical Programming Compu- tation, 2020. doi: 10.10077/112322000000011 2...-.... URL
612532-020--01732
12

---

Under review as a conference paper at ICLR 2021
Veselin Stoyanov, Alexander Ropson, and Jason Eisner. Empirical risk minimization of graphical model parameters given approximate inference. decoding, and model structure In Proc. of AISTA7S, 2011.
Ryutaro Tanno, Kai Arulkumaran, Daniel Alexander, Antonio Criminisi, and Aditya Nori. Adaptive neural trees. In International Conference on Machine Learning, pp. 6166-66666 6175. PMLR, 2019.
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, pp. 1625-1632, 2019.
Dwi Widyantoro, Thomas R Ioerger, and John Yen. An incremental approach to building a cluster hierarchy. In 2002 IEEE International Conference Data Mining, 2002. Proceedings., pp. 705-708. IEEE, 2002.
Yongxin Yang, Irene Garcia Morillo, and Timothy M Hospedales. Deep neural decision trees. arXiv preprint arXiv: 1806. 1806.06988 2018.
Yao-Liang Yu and Eric P Xing. Exact algorithms for isotonic regression and related. In Journal of Physics: Conference Series, volume 699, pp. 1-9, 2016.
Constantin Zalinescu. Convex analysis in general vector spaces.
World Scientific, 2002.
Tian Zhang, Raghu Ramakrishnan, and Miron Livny. Birch: an efficient data clustering method for very large databases. ACM sigmod record, 25(2)1003-114, 1996.
Tian Zhang, Raghu Ramakrishnan, and Miron Livny. Birch: A new data clustering algorithm and its applications. Data Mining and Knowledge Discovery, 1(2):141-182, 1997.
A APPENDIX
A.1 PROOF OF PROPOSITION 2
Let G C T be subset of (pooled) node indices. We seek to solve
arg min oER
Σ (a) = arg min
Σ 1/2(a - -n)
Σ
1/2(a- q
(11)
aE(o,1]
Note that the final summation implicitly depends the unknown But, regardless of the value of if qie S we and de is included in the sum, then qer must also be included by transitivity. We may therefore characterize the solution a" via the number of active incquality constraints k = =((itt)
a' I (..e) |- We do not know a*, but trivial to find by testing all possible values of k. For each we may find the set S(k) defined in the proposition. For a given k, the candidate objective is
(a) Σ 1/2(a n² +
Σ (L.))E(()
1/2(a - qa)²
(12)
LEG
and the corresponding a(k) minimizing it can be found by setting the gradient to zero:
a(k) Σieg Tht + E(an)ss()) qie |G|
1k(a) E(a (a)+))++++
Σ
(a- ==- =
IEG
(i.))S(()
(13)
Since [S(k) = and each increase in k adds non-zero term the objective, we must have Ji (a(L)) < J1 (a(2)) < (2((2)) < ... must take l to be small possible, while also ensuring the condition ((i,t) a(k) I qull k. or, equivalently, that a(k: > Qgaata.. The box constraints may be integrated at this point via clipping, yielding at =Projoo1) (a(k*)).
13

---

Under review as a conference paper at ICLR 2021
CVxpy
10
cuxpy
10
OuTs
10
10.4-
time (5)
10-39
time (S)
10-
10
10-3
10-22
10
10.41
(a) Fixed number of points 100
(b) Fixed tree depth
Figure 5: Comparison of Algorithm ds running time (ours) with the running time of Cvxpy with OSQP solver. takes values in range that covers common choices of batch size. Time and axis represented in logarithmic scale.
A.2 BENCHMARKING SOLVER TIMES
study the running time Algorithm depending on the number of data points n and the chosen tree depth D. We compare its solving time with the time needed by the popular convex optimization framework Cvxpy (Diamond Boyd 2016)] Agrawal et al.) (2018) to solve Problem with OSQP solver (Stellato et al. 2020 As Cvxpy based solvers implemented in Objective C and C implement our approach in C++ ++ for a fair comparison. We report the solving times Figure where we vary one parameter n or
time and fix the other. The algorithm that we specifically designed to solve Problem is indeed several magnitude faster than the considered generic solver.
A.3 FURTHER EXPERIMENTAL DETAILS
We tune the hyper-parameteed fixing the number of trials to 100. For all pack-propagation- based methods, we fix the learning rate to 0.001, use a scheduler reducing this parameter of a factor of 10 every 2 epochs where the validation loss has not improved, and fix the maximal number of epochs to 100 and patience equal 10 for early stopping. For our method, we further initialize the bias b E RI7 for the split function sp (x) (explicitly defining sœ(x) = (z) + b) to ensure that points are equally distributed over the leaves at initialization. We hence initialize the bias to minus the initial average value of the training points traversing each node: b, [m:
all methods with Optuna Bayesian optimizer (Akiba al. 2019),
Sp. ( > 0j.
Experiments tabular datasets as follows:
The other hyper--arameee for these experiments chosen
Ours: we tune D in (2.....6), 6). [1e33, 1e+3] with log- log-uniform draws, the number of
layers of the MLP L in {2.... 5] and its dropout probability uniformly in [0, 0.5), and the choice activation for the splitting functions as linear or Elu;
Optree-LS: we fix the tree depth D) 6;
we tune D in (2...., 10), feature rate uniformly in [0.5, 1), minimal impurity decrease in [0, 1), a log-uniformly [1e-16, le+2] and splitter chosen between best or random;
CART:
Node and XGBoost: all results are reported from Popov al. (2019), where they used the same experimental set-up;
DNDT: we tune the softmax temperature uniformly between (0, 1] and the number of feature cuts in {1,2);
NDF: we tune D in . 6} and fix the feature rate to 1;
We ran experiments with the commercial solver GUROBI Gurobi Optimization, 2020 but didn't 't find
significant differences with using OSQP.
14

---

Under review as a conference paper at ICLR 2021
Table 4: Number of parameters for single-tree methods tabular datasets.
method
YEAR
MICROSOFT
YAHOO
CLICK
HIGGS
CART
164
58
883
DNDT
4096
OPTREE-LS
3060
Single
NDF-1
78016
47168
ANT
179265
17217
Ours
15892
19158
59131
255
ANT: for the sake of fairness, we choose as transformer the identity function, as router linear layer followed by the Relu activation and with soft (sigmoid) traversals, and solver a MIP with I. hidden layers, as defined for our method; we hence tune in (2.....93 5 and its dropout probability uniformly in [0, 0.5), and fix the maximal tree depth D we finally fix the number of epochs for growing the tree and the number of epochs for fine-tuning it both 50.
Experiments on small datasets We chose the hyper-parameters as follows:
Ours: we tune D in f2...., 6).
in [1e-3, 1e+3] with log-uniform draws, and make use of linear predictor and of linear splitting functions without activation;
Optre--MPP/Optre-LLS we fix the tree depth D 6;
GOSDT: we tune the regularization parameter À in [1e-3, 1e+3] with log-uniform draws, and set accuracy as the objective function.
Experiments hierarchical clustering For this set of experiments, make of a linear predictor and linear splitting functions without activation. The other method are chosen follows: tune D in (2...., 6). in [1e-3, le+3] with log-uniform draws. The results of the baselines are reported from Monath et al. (019).
of our
A.4 ADDITIONAL EXPERIMENTS
In Figure 6 we represent the average test Error Rates or Mean Square Error as a function of training time for each single-tree method on the tabular datasets of 4. Notice that our method provides the best trade-off between time complexity and accuracy over all datasets. In particular, achieves Error Rates comparable on Click and significantly better on Higgs w.r.t. NDF-1 while being several times faster. Table shows that this speed-up principally due to smaller number of model's 's parameters. Despite having model sizes comparable ANT's ones Microsoft and Yahoo, our method is significantly faster than this baseline as it offers an efficient way for optimizing the tree structure (via the optimization of pruning vector a). In comparison, ANT needs to incrementally grow trees in a first phase, to then fine-tune them in second phase, resulting in a computational overhead.
15

---

Under review as a conference paper at ICLR 2021
0.48
method
0.32
method
CART
CART
Error Rate
NDF-1
Error Rate
0.30
NDF-1
Ours
Ours
0.28
DNDT
0.26
0.38
0.36
0.24
0.34
0.22
500
1000
1500
25:00
3000
3500
10000
20000
30000
40000
training time (s)
training time (s)
(a) Click
(b) Higes
0.62
method
method
Mean Square Error
95.0
CART
Mean Square Error
CART
92.5
ANT
ANT
Ours
0.60
Ours
87.5
85.0
0.59
60.0
77.5
0.57
training time (s)
training time (s)
(c) Year
(d) Microsoft
method
Mean Square Error
0.68
CART
ANT
0.65
Ours
0.64
0.82
1000
2000
3000
4000
training time (s)
(e) Yahoo
Figure 6: Average (a.b) Error Rate (c-e) Mean Square Error vs average training time required by each method.
16


Reviews:
[{"review_id": "sa6giDZLUDO", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "The problem definitions are not somewhat unclear. It seems that (1)-(7) is to find a pruning of the given tree, which are not explicitly mentioned. \n\nIt is not nontrivial that the problem (1) leads to a tree. It would be necessary to have some proposition that ensures the desired properties (e.g., solution represents a tree) of the solution or cites such previously known ones.\n\nThe obtained solutions in (3)-(7) are not discrete and how to round up continuous solutions to discrete ones are not shown. \n\nAs a summary, the current writing lacks important information such as the correctness of the solutions, which significantly reduces the contribution of the paper, even if the experimental results look better than previous work.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "aTNHdmykDIT", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "Summary: The paper provides an interesting way to learn binary trees that is faster than generic solvers of MIP. The trick is to use gradient-based methods for a new sparse relaxation of MPI. Authors compare their method to generic solvers and find a substantial improvement on runtime. This is certainly important for scalability.\n\nThe paper overall is of good quality. The story of the work is well-written which makes the contributions easier to digest.\n\nIn terms of theoretical contributions, the work is \"weak\" in the sense that the main result follows from a simple relaxation. However, authors show strong empirical evidence that their method is faster and competitive to existing results. Thus, in terms of scalability, the results are relevant.\n\nIf my understanding is correct, the appealing aspect of their method is the runtime. In the experiments section, authors show a huge gap in runtime between cvxpy and their implementation. I wonder if cvxpy is mostly implemented in Python, given that the authors implemented their method in C++, I would expect a better performance just from that. Although, the huge gap in runtime suggests that it wouldn't matter.\n\nThe topic is also of good significance given that decision trees are still widely used in practice. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "YsYqIvhv_L", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "The given paper describes a novel approach of learning binary trees using a differentiable relaxation of MIP. For that matter, authors describe their approach of tree traversal for the given input x and a complete binary tree of depth D. This problem is formulated as MIP which is relaxed to make it differentiable. This MIP is then reformulated to learn a tree structure (i.e. tree pruning). Finally, a decision node parameters are optimized using backpropagation. The algorithm alternates between tree structure learning using relaxed MIP and tree parameters learning using SGD. \n\nMajor advantageous:\n\n  . The proposed method is interesting and addresses the tree learning algorithm from different perspective. I liked the idea of MIP relaxation and the proposed algorithm to solve the QP (using isotonic regression).\n\n  . It is nice that the method is quite generic and can be applied to both (semi)supervised/unsupervised (e.g. clustering) problems.\n\nMajor concerns:\n\n  . First of all, I found this paper is hard to follow and understand. Therefore, I have a couple of fundamental questions/comments regarding methodology:\n\n    - The overall obj function (eq. 10) is minimized using backpropagation over decision node parameters \\theta. However, in order to compute gradients w.r.t. \\theta, we need to compute q(x) which is, I believe, non-differentiable (it involves max function). \n\n    - Are you solving the tree program (eq. 3) at each mini-batch update or it is done only once at the beginning of the minimization problem 10? Providing a pseudocode of the overall algorithm would be beneficial.\n\n    - In conventional trees, a tree output is given by its leaf. However, here it seems the final prediction is obtained by f(.) and I don't understand why? What is the use of f(.)? I know that it is a linear function or MLP. But, why it takes z and x as arguments and makes the final prediction. It is not well described in the paper. By the way, figure 1 is not referenced anywhere...\n\n  . Given all relaxations in the final algorithm, my impression is that these trees are look like a regular soft trees but with tree structure learning capability. \n\n  . Experiments lack sufficient evaluations (for regression and classification). For regression, comparison is performed only against CART. Moreover, why depth of the tree for CART is limited to {2,...,6}? I believe that it heavily under-represents CART since it is known that the depth for such trees should be sufficiently large. Most importantly, I strongly suggest authors to include more advanced baselines (e.g. [1,2,3]) for both classification and regression. Moreover, resulting table should contain model sizes in terms of number of parameters, at least (e.g. I'm confident that CART trees will be much smaller).\n\n[1] Tanno, R., Arulkumaran, K., Alexander, D. C., Criminisi, A., and Nori, A. Adaptive neural trees. ICML 2019.\n\n[2] Carreira-Perpinan, M. A. and Tavallali, P. (2018). Alternating optimization of decision trees, with application to learning sparse oblique trees. NeurIPS 2018.\n\n[3] A. Zharmagambetov and M. A. Carreira-Perpinan (2020): Smaller, More Accurate Regression Forests Using Tree Alternating Optimization. ICML 2020\n\nMinor concerns: \n\n  . I believe that the method cannot be used to train a regular axis-algined trees, i.e. to force each node to use only one feature. \n\n  . NDF baseline is always performs better than the proposed approach. I believe ANT[1] will perform even better. Given all of them have similar model sizes (including the proposed method), I don't see any practical benefits of the proposed method over the others.", "extra_scores": {}, "extra_text": {}}, {"review_id": "YiG1x_10a8q", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "## Summary\n\nThis paper presents a new approach to learn decision trees via sparse relaxation. The approach starts from a mixed-integer program that can simultaneously induce and prune optimal decision trees from data. The proposed technique aims to solve a continuous relaxation of this problem by combining (1) a tree induction routine, which uses isotonic optimization with (2) an efficient implementation that avoids the need for automatic differentiation. The paper includes experiments on publically available datasets, showing how the decision trees produced via sparse relaxation to decision trees produced using other tree induction approaches.\n\n## Pros\n\n- Interesting new technique for a canonical problem. \n- Proposed method produces trees that appear to perform well on classification, regression, and clustering problems.\n- Paper showcases a deft approach to modern algorithm design\n\n## Cons\n\n- No theory or empirical results to characterize the optimality of trees produced via sparse relaxation. \n\n## Rating\n\nI have awarded the paper a 6, though I am open to increasing my score if the authors can address some of the questions I include below. Overall, my chief concern about this work is that it does not include any evidence pertaining to the optimality for trees produced via sparse relaxation. In effect, the main argument for the proposed sparse relaxation technique is that it produces trees that perform well on five datasets. I believe that my concerns should be easy to address – either by reporting the optimality gap of the trees in the experimental results, or by including comparisons with methods that are guaranteed to find optimal trees. \n\n\n##  Questions / Comments\n\n1. Have you evaluated the optimality of solutions of your method with respect to the exact tree-fitting optimization problem – i.e., problem (10) where the tree is a solution to the MIP in (2). All decision trees should be feasible with respect to this problem. In turn, it should be possible to report their \"optimality gap.\" Reporting the optimality gap would provide some evidence to evaluate the integrity of the decisions you made in algorithm decision. It could also showcase the value of sparse relaxation as a feasibility heuristic for the MIP-based approach. \n\n2. In the experiments, what is the relative optimality gap of the solutions found by OPTREE? Is it finding certifiably optimal solutions (i.e., solutions with a relative optimality gap of 0%)? If not, it would be useful to include comparisons on a tabular dataset that is small enough for OPTREE to find a certifiably optimal solution. Two datasets to consider here are (1) UCI Mushrooms dataset (which is linearly separable and should be easy for all methods), and (2) the COMPAS dataset (also small, but not linearly separable). \n\nFWIW, the statement that \"Bertsimas & Dunn (2017) phrased the objective of CART as a MIP that could be solved exactly\" is misleading as it suggests that Bertsimas & Dunn (2017) are able to recover globally optimal solutions to the MIP. This is not the case. In many datasets, the proposed method can only find feasible solutions that perform well but have large optimality gaps. \n\n3. I am wondering why the authors did not consider the following methods to train optimal decision trees in their experiments:\n\n- [Optimal Sparse Decision Trees](https://papers.nips.cc/paper/8947-optimal-sparse-decision-trees)\n- [Generalized and Scalable Optimal Sparse Decision Trees](https://proceedings.icml.cc/static/paper_files/icml/2020/3364-Paper.pdf)\n\nThis seems like a weird oversight given that: (i) the paper includes references to both of these works; (ii) both works include reliable implementation that could easily be used to train decision trees in the experimental section (see e.g., https://github.com/Jimmy-Lin/GeneralizedOptimalSparseDecisionTrees). \n\nThe paper currently references both of these works in a way that suggests that they are MIP-based methods. This is misleading. These methods are able to fit certifiably optimal decision trees through specialized algorithms that do not require solving a MIP. I recognize that there has to be a limit to the number of experiments that one can perform. That being said, the trees produced by these methods are an important baseline to include in the experiments since they appear to outperform those produced by MIP-based approaches.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The main problem as flagged by reviewers is the lack of formal evidence that the approach is a right one to carry out. Decision tree induction has early been the subject of formal studies in ML, whether in statistics (Friedman et al.) or ML (Kearns et al.). It is a bit sad that a new approach that relies on a much different standpoint on the problem and modelling of tree classification (Section 3, R2), with experimental results recognized by reviewers (R3, R4) is not accompanied by formal analyses on par with SOTA for related approaches (R3, R1). I would strongly suggest the authors fit in a few more Lemmata, either to follow up on specific problems (R1). The paper would tremendously benefit from extensive connections with the existing theory, be it from the generalization and overfitting standpoint (R2, remark #6) or the choice of the appropriate best contender using the boosting literature. Decision was taken not to accept the paper but I would very strongly encourage the authors to revise the draft.

Decision: Reject