Learning Accurate Decision Trees with Bandit Feedback via Quantized Gradient Descent
Authors: Ajaykrishna Karthikeyan
Naman Jain
Nagarajan Natarajan
Prateek Jain
Venue: Accepted by TMLR ()

Abstract: Decision trees provide a rich family of highly non-linear but efficient models, due to which they continue to be the go-to family of predictive models by practitioners across domains. But learning trees is challenging due to their discrete decision boundaries. The state-of-the-art (SOTA) techniques resort to (a) learning soft trees thereby losing logarithmic inference time; or (b) using methods tailored to specific supervised learning settings, requiring access to labeled examples and loss function. In this work, by leveraging techniques like overparameterization and straight-through estimators, we propose a unified method that enables accurate end-to-end gradient based tree training and can be deployed in a variety of settings like offline supervised learning and online learning with bandit feedback. Using extensive validation on standard benchmarks, we demonstrate that our method provides best of both worlds, i.e., it is competitive to, and in some cases more accurate than methods designed specifically for the supervised settings; and in bandit settings, where most existing tree learning techniques are not applicable, our models are still accurate and significantly outperform the applicable SOTA methods.

Published in Transactions on Machine Learning Research (09/2022)
Learning Accurate Decision Trees with Bandit Feedback via Quantized Gradient Descent
Ajaykrishna Karthikeyan'l Deportment of Computer Science University of Illmoois Urbana- Champaign
ak ak76@rlknoiisedd edu
Naman Jain"t
Department Electrical Engineering and Computer Science University of California, Berkeley
Nagarajan Natarajan
negarajjn.@micrrooof..com
Microsoft Research, India
Prateck Jain
prajuin Trajuiin@goggle.coom
Google Research, India
Reviewed on OpenReview: https: // openreview. net/ forum? id= wd=
Abstract
Decision trees provide rich family of highly non-linear but efficient models, due to which they continue to be the go-to family of predictive models by practitioners across domains. But learning trees is challenging due to their discrete decision boundaries. The state-of-the- art (SOTA) techniques resort to (a) learning soft trees thereby losing logarithmic inference lime; or (b) using methods tailored to specific supervised learning settings, requiring access to labeled examples and loss function. In this work, by leveraging techniques like overpa- rameterization and straight-through estimators, we propose a unified method that enables accurate end-to-end gradient based tree training and can be deployed in a variety of settings like offline supervised learning and online learning with bandit feedback. Using extensive validation standard benchmarks, demonstrate that our method provides best of both worlds, i.c., it is competitive to, and in some cases more accurate than methods designed specifically for the supervised settings; and in bandit settings, where most existing tree learn- ing techniques are not applicable, our models are still accurate and significantly outperform the applicable SOTA methods.
1 Introduction
Decision trees are an important and rich class of non-linear ML models, often deployed in practical ma- chine learning systems for their efficiency and low inference cost. They can capture fairly complex decision boundaries and are state-of-the-art (SOTA) in several application domains. Optimally learning trees is a challenging discrete, non-differentiable problem that has been studied for several decades and is still receiving
active interest from the community GGou et al. 2019 Hazimeh et al. 2020 Zantedeschi et al. 2021
Most of the existing literature studics tree learning in the context of traditional supervisod settings like clas- sification Soureira-Perpinkee and Tavallali 2018) and regression /Zharmagambetov and Carreira- Perriia- 2020), where the methods require access explicit labeled examples and full access to a loss function. How- ever, in several scenarios might not have access to labeled examples, and the only supervision available might be in the form of evaluation of the boss/rrward function at given point. One such scenario is the
Equal Contribution
Work done while author was Microsoft Research, India

---

Published in Transactions on Machine Learning Research (09/2022)
"bandit feedback" setting, that often arises in real-world ML systems (e.g., recommender systems with click- leedback), where the leedback for the deployed model is in the form of loss/ reward. The bandit setting has been long-studied both in the theoretical dieoretical/opdimizaton /optimization communities as well as in the ML community Dann ct al. 2008 Dudik et al. 2011 Agarwal ct al.] 2014 Shamir 2017). The Vowpal Wabbit (VW) library is exlensively used by practitioners for solving learning problems in this setting.
So, in this work, we address the question: can we design a general method for training hard decision trees, that works well in the standard supervised learning setting, well in settings with limited supervision? In particular, we focus online bandit feedback in the presence of context. Here, at each round the contex/exxampe
learner observes or continuous space (regression) for which it then receives a loss, which must be minimized. Since the structure of this loss function is unknown to the learner, it is referred to as black-box loss, in contrast to the loss observed in the supervised setting where the entire structure is known to the learner. Notice that this loss function can be evaluated only once for an example. Hercafter, we will refer to this sctting in the paper simply the bandil selling or the bondil. feedbback selling.
picks an action/prediction either from a discrete space (classification)
Recently, several neural techniques have been proposed to improve accuracy of tree methods by training with differentiable models. However, either their (Yang et al.
2018 Lee and Jaakkola 2020 accuracies do
not match the SOTA tree learning methods on baseline supervised learning tasks or they end up with "soft" "
decision trees (rsoo et al. 2012 Frosst and Hinton 2017 Biau et al. 2019 Tanno et al. 2019 Popov et al.
2020) which is not desirable for practical settings where inference cost may be critical. Using annealing
techniques to harden the trees heavily compromises on the accuracy (as seen in Section 5) On the other
hand, there is a clear trade-off between softness (and in turn inference cost) and performance in SOTA tree methods (aazimeh et al. 2020 which try to minimize the number of leaves reached per example (Section 5
SOTA (hard) tree learning methods (Carreira-Perpiáán and Tavallali 2018 Hehn et al. 2019 Zharmagambe- tov and Parreira-Perpinan, 2020), based on alternating optimization techniques, yield impressive performance in the batch/fully supervised setting (as seen in Section 5, but their applicability drastically diminishes in more general bandit settings where the goal is to achieve small regrel with few queries to the loss func- tion. It is unclear how to extend such methods to bandit settings, as these methods optimize over different parameters alternatively, thus requiring accoss to multiple loss function evaluations per point.
We propose simple, end-to-end gradient-based method "Dense Gradient Trees" (DGT) F that gives best of both worlds- - (1) logarithmic inference cost, (2) significantly more accurate and sample-efficient than general methods for online settings, (3) competitive to SOTA tree lcarning mothods designed specifically for supervised lasks, and (4) easily extensible to ensembles that outperform widely-used choices by practitioners. DGT appeals to the basic definition of the tree function that involves a product over hard decisions at each node along root-to-leaf paths, and arg max over paths. We make three key observations regarding the tree function and re-formulate the learning problem by leveraging successful techniques from deep networks training literature: 1) the path computation AND function can be expressed in "sum of decisions" form rather than the multiplicative form which has ill-conditioned gradients, 2) we can overparameterize the tree model via learning a lineur deep embedding of the data points without sacrificing elficiency or the tree structure, and 3) hard decisions at the nodes can be enforced using nuantzzatoonawwar aware gradient updates.
The reformulated tree learning problem admits efficient computation of dense gradients with respect to model parameters leveraging quantization-wware (noisy) gradient. descent and gradient estimation via per- turbation. We provide algorithms for standard supervised learning (DGT) and bandit (DGT-Bandit) settings, and extensively evaluate them on multiple classification and regression benchmarks, in supervised as well as in bandit settings. On supervised tasks, DGT achieves SOTA accuracy on most of the datasets, comparing favorably to methods designed specifically for the tasks. In the bandit setting, DGT-Bandit achieves up to 30% less regret than the SOTA method for classification and up to 50% less regret than the applicable bascline for regression.
IIuformally, hard tree is one where during inference, input example decisively moves down to single child at internal node, thus landing on a single leaf finally. In contrast, an input example in soft tree is probabilistically distributed over children of internal node, and hence over leaves of the tree as well.
2 Source code is available at httpp://gittaab.com/iiii com.m//oooooctt/f///ggt
2

---

Published in Transactions on Machine Learning Research (09/2022)
Our key contributions are: 1) A unified and differentiable solution for learning decision trees accurately for practical and standard evaluation settings, 2) competitive (or superior) performance compared to SOTA hard decision tree learning methods on a variety of datasets, across different problem settings, and 3) enabling samplo-efficien tree learning in the online, bandit feodback sctting without exact information on the loss function or labels.
1.1 Related Work
Several lines of research focus on different aspects of the tree learning problem, including shallow and sparse trees (Kumar et al. (017), efficient inference (Jose et al. 2013), and incremental tree learning in streaming scenarios (Domingos and Hulten 2000; Jin and Agrawal 2003 Manapragada et al.) 2018 Das et al., 2019)
(where labels are given but arrive online). The most relevant ones are highlighted below.
Non-greedy techniques: "Tree Alternating Optimization" (TAO) is a recent SOTA non-greedy technique for learning classification (Carreira-erppnnaa and Tavallali 2018 and regression (Zharmagambetor and Carreira-Perpinan. 2020) trees. It updates the nodes at given height (in parallel) using the examples routed to them in the forward pass while keeping the nodes in other heights fixed. The gradients during backpropagation are "sparse" in that each example contributes to O(h) updates. This poses a challenge from a sample complexity perspective in the online setting. In contrast, DGT performs "dense" gradient updates, i..,, with one examplc's one (quantized) forward pass, O(2h) model parameters can be updated in our backpropagation. Interestingly, we find DGT achieves competitive results to TAO even in the batch setting (see Section 5)- Norouzi al. (2015) optimizes a (loose) relaxation of the empirical loss; it requires Ohh) loss evaluations per ezample (as against just 1 in DGT) to perform gradient update, it does not apply to bandit settings. [Bertsimas and Dunn (2017); Bertsimas et al. (2019) formulate tree learning as mixed integer linear program (II.P) but their applicability is limited in terms of problem settings and scale. LCN Lee and Jaakkola (020)) uses h-layer ReLU networks to learn oblique trees of height h. But, for a given height, their model class admits only a subset of all possible trees which seems to deteriorate its performance (see Section 5).
Soft trecs/Neural techniques: Several, mostly neural, techniques (Jodan and Jacobs 1994
Irsoy et al.
2012
Kontschieder et al. 2015 Balestriero 2017 Frosst and Hinton 2017 Biau et al. 2019 Tanno et al.
2019
Popov et al. 2020) try to increase the accuracy of decision trees by resorting to soft decisions and
complex internal nodes and end up producing models that do not have oblique tree structure (Definition The recently proposed (Zantedeschi et al.) 2021) embeds trees as layers of deep neural networks, and relaxes mixed ILP formulation to allow optimizing the parameters through a novel "argmin different iation" method.
In Jordan and Jacobs [1994]; Irsoy et al. (2012): Frosst and Hinton (2017), all root-to-leaf path probabilities have to be computed for given example, and the output is weighted sum of decisions of all paths. Two recent tree learning methods are notable exceptions: 1) Hehn et al. (2019) uses an E-M algorithm with sigmoid activation and annealing to learn (hard) trees, and 2) TEL (Hazimeh et al.) 2020) is a novel smooth- step activation function-basee based method that yields a small number of reachable leaves at the end of training, often much smaller than O(2*) ) for probabilistic trees. However, the inference cost of the method is relatively much larger than ours, to achieve competitive accuracy, as we show Section 5.3
Bandit feedback: Contextual bandit algorithms for this setting allow general reward/ seward/loss functions but are mostly applicable to discrete output domains like classification (Agarwal et al. (2014)); e.g. Féraud discretized input features, and Elmachtoub et al. (2017) learns a separate decision tree for every action via bootstrapping. In contrast, DGT uses noisy gradient estimation techniques [Flaxman et al. 2005 Agarwal et al. 2010) (logether with our tree learning reformulation) to provide an accurate solution for both bandit classification and regression settings.
et al. (2016) learns an axis-aligned decision tree/forest
2 Problem Setup
Denote data points by x E Rd. In this work, we focus on learning oblique binary decision trees.
Definition (Oblique binary decision tree). An oblique binary tree of height h represents a piece-wise constant function f(x; W. @) Rd + RK parameterized by weights Waz E Rd by E R at (i, node (j-th node at depth i) compuling decisions of the form (Wej, x) bij > 0, that decide whether must traverse the
3

---

Published in Transactions on Machine Learning Research (09/2022)
left or right child next. For classification, associate parameters 0, E RR at j-th leaf node, encoding scores probabililies for each of the K classes. For regression, 0j E IR (K=1) 1) is the prediction given by the j-th leaf node.
We devise algorithms for learning tree model parameters (W, )) in two different settings.
(I) Contextual Bandit setting. In many practical settings, e.g. when ML models are deployed in online systems, the learner gets to observe the features x, but may not have access to label information; the learner only observes a loss (or reward) value for its prediction on x,- We have zeroth-order access to 8: f(x;; W) + R+, i.. is an unknown loss function that can only be queried at a given point (W, O;). The goal then to minimize the regret:
a Σ (,, n
min 1 W. n
([(x;
(II) Supervised learning. This is the standard setting in which, given labeled training data (x,, y:). where yi is the label of Xi, and a known loss e: (f(x; W,O),)) R+, the goal is to learn decision tree that minimizes empirical loss on training data:
min W.
Σ (, + 1 (W, W. O),
(1)
where (-) a suitable regularizer for model parameters, and À >> is the regularization parameter. We consider both regression (with squared loss) and classification (with multiclass 0-1 loss).
Our method DGT (Section provides end-to-end gradient of tree prediction with respect to the tree parameters, so can combine the tree with any other network (i.e., allow (g(x;; W. θ), where g and e can be neural networks) or loss function, and will still be able to define the backpropagation for training the tree. So, in addition to the above loss functions and supervised learning setting, DGT readily applies to a more general set of problems like multi-instance learning (Dietterich et al. 1997.. semi-supervised learning (Van Engelen and Hoos 2020), and unsupervised learning (Chapter 14, Friedman al. (2001)
We also consider forest version of DGT (called DGT-Forest) in Section 5
Notation: Lowercase bold letters x, w, etc. denote column vectors. Uppercase bold letters (e.g. W, denote model parameters. x(i), w(j) denote the i-th and the j-th coordinate of x and w, respectively.
3 Our Tree Learning Formulation
Learning decision trees known to be NP-hard Siieling differentiable optimization problem. SOTA methods typically learn the tree greodily (Breiman et al. 1984 Quinlan 2014) or using alternating optimization at multiple depths of the tree (Carreira-Perpinán and Taval- 2020).. These methods typically require full access to the loss function (see Related Work for details). We remedy this concern by introducing simple technique that allows end-to-end computation of the gradient of all tree parameters. To this end, we first introduce a novel flexible re-formulation of the standard tree learning problem; in Section 4 we utilize the re-formulation to present efficient and accurate learning algorithms in both bandit and supervised (batch) settings.
2003) due to the highly discrete and non-
lali 2018 7hharagammbeoov and Carreira-Perpinaa
Consider a tree of height h. Let I(i, denote the index of the l-th leaf's predecessor in the i-th level of the tree; e.g., for all i, I(t,l) 0 if is the left-most leaf node. Also, define S(i, as:
-1, I-th leaf e left subtree of node 1(i, l),
S(1,1) =
+1, otherwise.
4

---

Published in Transactions on Machine Learning Research (09/2022)
Recall that Waj E R and by E R are the weights and bias of the node at depth h, and 0, are the parameters at leaf I. Now, the decision f(x; W.O Q) can be written as:
f(x W) - Σ
(x; w)0, where
(2)
1=0
(x:: W) II
((Ws,)(,))))) +b.nc.))(((.1))
i=0
In decision trees, o() is the step function, i.e.,
Step (a) 1, a 0, and astep(a) = 0, if a 0.
(3)
This hard thresholding Step presents a key challenge in learning the tree model. standard approach is to relax step via, say, the sigmoid function (Sethi 1990 Kumar et al. 2017 Biau et al. 2019 and model the tree function a distribution over the leaf values. Though this readily enables learning via gradient descent-style algorithms, the resulting model is not a decision tree as the decision at each node soft thus leading to ezponential (in height) inference complexity. Also, using standard methods like anncaling to convert the soft decisions into hard decisions leads to significant drop in accuracy (see Table 1
Applying standard gradient descent algorithm to solve [ has other potential issues besides the hard/soft decision choices with the choice of a. In the following, we leverage three simple but key observations to model the function f in ( which lets us design elficient and accurate algorithms for solving ( with any general, potentially unknown, loss function
3.1 AND gradients
The di function
2 to compute the AND of the decisions along a root-to-leaf path has a multiplicative form, which commonly used in tree learning formulations (Kumar et al.) 2017). When we use the relaxed sigmoid function for a, this form implies that the gradient and the Hessian of the function with respect the parameters are highly ill-conditioned (multiplicationn of sigmoids). That is, in certain directions, the Hessian values can be vanishingly small, while others will have scale of O(1). It is hard to reconcile the disparate scales of the gradient values, leading to poor solutions which we observe empirically well (in Section 5). We leverage simple but key observation that can be equivalently written using sum instead of the multiplicative form:
q (x: W)
Σ a (( x) + ((nn.)) h).
(4)
Proposition 1. The path function in is identical to the definition in 2 when o := Stepp in
(3)
The proposition follows directly from the definition of dstep qi term in Eqn. 2 evaluates to 1 iff all terms in the product evaluate to (corresponding to the decisions made along the root-to-lcaf path); Similarly in Eqn. (4) (which operates on the same terms as that of in Eqn. (2) evaluates to 1 iff each term in the sum is 1, because the sum will then be h, which after the offsset -h yields according to the definition of Sstep Therefore the two definitions of qi are equivalent.
The gradient of qi in is sum of h terms each of which is a product of only two sigmoids, the problem should be much better conditioned. Our hypothesis is validated empirically in Section 5
3.2 Overparameterization
Overparamoterization across multiple layers is known to be an effective tool in deep learning with strong
empirical and theoretical results (Allen-Zhm Zhu al. 2019 Arora et al., 2019 Sankararaman al.) 22020), and is hypothesized to provide strong regularization effect. While large height decision trees can seem "deep"
5

---

Published in Transactions on Machine Learning Research (09/2022)
and overparameterized, they do not share some of the advantages of deep overparameterized networks. In fact, deeper trees seem to be harder to train, tend to overfit and provide poor accuracy.
So in this work, we propose overparameterizing by learning "deep" representation of the data point itself, before it being fed to the decision tree. That is, we introduce L linear fully-connected hidden layers with weights W(1) E Rd xd W(2) E (d2xxd,,.. ..... w!L-1) E pdde-1xde-,, w(() E -22-1xx=-1,, where d; are syper-paramcters and apply tree function f to f(W(-)) w W(L), )). Note that L is the number of hidden layers we use for our overparamellrizztion.
Note that while we introduce many more parameters in the model, due linearity of the network, each node still has a linear decision function: (w (w!)), w(1-1))((122) (.))) (Wij. where Wij = (w(4-))((--3)... W()) Tw any feature transformation during inference.
(f) Thus, we still learn an oblique decision tree (Def. I and do not require
Remark 1. We emphasize that despite using overyorameterizationn, we finally obtaon standard oblique deci- sion tree (Definition[) [] with linear model at each internal node. In particular, we do not require any feature transformation at the inference time, unlike the tree learning approaches of Kontschieder et al. (2015); Tanno et ol. 2019) that learn deep representations thereby increasing the model size and inference time.
Given that linear overparameterization works with eraclly the same model class, it is surprising that the addition of linear layers yields significant accuracy improvements in several datasets (Section 5.4 Indeed, there are some theoretical studies (Arora et al. 2018)) on why linear networks might accelerate optimization, but we leave a thorough investigation into the surprising effectiveness of linear overparameterization for future work.
3.3 Quantization for hard decisions
As mentioned earlier, for training, a common approach is to replace the hard datep with the smooth sigmoid, and then slowly anneal the sigmoid to go towards sharper decisions (Josc et al.) 2013 Kumar et al. 2017 That is, start with a small scaling parameter 8 in sigmoid function (a(a) == 1+exp(-s a}> and then slowly increase the value of s. We can try to devise a careful anncaling schedule of increasing values of s, but the
real issue such a training procedure is that cannol output a hard tree in the end we still need to resort heuristics convert the converged model a tree, and the resulting loss in accuracy can be steep (see Table D.
Instead, use techniques from the quantization-awalt neural network literature (Rastegari et al. 2016 Courbariaux et al.] 2016 Hubara et al., 2016 Esser et al.] (020),, which uses the following trick: apply quantized functions in the forward pass, but use smooth activation function in the backward pass to propagate appropriate gradients. In particular, we leverage the scaled quantizers and the popular "straight- estimator' to compute the gradient of the hard step function (Rastegari et al. 2016: Courbariaux et al. 2016) (discussod in Section 4. Note that, unlike typical quantized neural network scenarios, our sctting requires (1-bit) quantization of only the a functions.
Finally, using the aforementioned three ideas, we reformulate the tree learning problem
as:
n Σ (f((; W, O), + ( (W,)). O),
min Wmm) G n
(5)
W ((-) W()),
s.t.
f(x; W. θ as in 2 (xx; W) as
4 Learning Algorithms
We now present our Dense Gradient Tree, DGT, learning algorithm for solving the proposod decision tree formulation ( in the bandit setting introduced in Section 2 Extension to the fully supervised (batch) setting using standard mini-batching, called DGT, presented in Appendix A

---

Published in Transactions on Machine Learning Research (09/2022)
Algorithm DGT-Bandit: Learning decision trees in the bandit setting
Input: height h, max rounds T, learning rate 77, loss (A, Preg), overparam. hidden dim d,, [T]
2: Output: Tree model W. e R2"*
3: Init: w E Rdixa, w (Raaxd, W E -(e=-1) Oo E R2 x randomly.
4: for round == 1, do
5: Get (unlabeled) example X 1] // with bias
0, f(x:; W,-1, 0 via (2) and dstep in 3 // compute the tree prediction
01 0,, for regression,
1, by delu.
sampled acc. to (7.. for classification.
8:
derivative of E at D1 via (regression) gradient computed
9:
1/ bandit feedbock
S
(classification)
10:
IV w(m) f. Vef) }- = BackBropp
W 1-1 (-1)
W m)) w(m! g. V. Win) f ndV W(m) @ Prog (W, 0), for m 1,2,.....
11:
12:
θ = -
ve. nvVe rog W
Algorithm 2 Backkrop
Input: x, W, O = 0 R²* (K=1) Wwim W, O), Vos(x; W,
Output:
3: Gradient with respect to O:
4: Let = arg max, qi (x; W)
5:
Vof(x; W, 0) = et. (standard basis vector).
Gradient with respect to W(m), =,2,..... L:
7: Let a (. (w()) E ER²-
Let Oij denote the entry of a corresponding to internal node (i.j)
9: Let (x; W) = Ei
m=u sign(
Wooddd, V Wi (x; W) Σ ((i,1) Vaanaa // Use slruight-through estimalor for the inner
10:
in
11:
Let = Σ, exp (x; W))
12:
Let Σ exp (x: W)
13:
W(m) [(x W = (1/=) - (0: (01- 0/=) exp (x
W) // Use SOPTMAX for the
outer in
Recall that in the bandit sctting, the learner observes the features x, at the ith round (but not the label) and a loss (or reward) value for its prediction 9s. The training procedure, called DGT-Bandit, is presented Algorithm [ It is the application of gradient descent problem ( The corresponding backpropagatton step is presented in Algorithm 2 There two key challenges in implementing the algorithm: (a) enforcing hard thresholding Step function discussed in Section g and (b) learning the tree parameters with only black-box access to loss l and no gradient information.
(a) Handling stepp In the forward pass (Line 6 of Algorithm 1 we use astep defined 3 compute the tree prediction. However, during back propagation, we use softer version of the decision function; see Algorithm 2 In particular, consider the following variant of the qi function in the backward pass, that applies SOFTMAX for the outer in
h-
(x; W) x exp
Σ 1=0
sign (Wi, x) + b..n)))((..))

---

Published in Transactions on Machine Learning Research (09/2022)
where the normalization constant ensures that Σ (x; W) = 1, and sign(a) st 1. By introducing
SOFTMAX, we can get rid of the offset -h in (4 To compute the gradient of the sign function, we use the
straight-through estimator (Bengio et al. 2013 Hubara et al. 2016) defined as: de of Algorithm 2).
Ssig((a)
| (Line 10
Remark 2. While we use the gradient of the SOFTMAX operalor in Tt for updaling W porameters, we use hard arg max operator for updating & parometers (as in Line of Algorithm
(b) Handling bandit feedback. The problem of learning with bandit feedback is notoriously challenging and has long line of remarkable ideas (Flaxman et al. 2005 Agarwal et al. 2010 While can view the problem a direct online optimization over the parameters W, O it would lead to poor sample complexity due to dimensionality of the parameter set. Instead, we leverage the fact that the gradient of the prediction 0, - [(; W, () with respect to the loss function can be writlen down as:
Vw.ee W, 0)) = (0.) Vw.ef(x;W) W.
66)
Now, given x and O, we can compute Vw,e/(x; W, θ) exactly. So only unknown quantity (0::) which needs to be estimated by the bandit/ pooittoiiiit proint-wise feedback based on the learning setting. Also note that in this case where l' estimated using one loss feedback, the gradients are still dense, i.e, all the parameters are updated as Ww,ef is dense; Lines 11 and 12 of Algorithm I
Classification setting: This is standard contextual multi-armed bandit setting (Allesiardo et al. 2014), where for a given x, the goal is to find the arm to pull, i..., output a discrete class for which we obtain a loss/reward value. So, here, O E IRK and the prediction is given by sampling an arm/class E [K] from the distribution:
~~ Pa: (k(k) (1 8)1 arg max (k') 5/K,
(7)
k'
where 5 > 0 is exploration probability. For the prediction ú. we obtain loss E(g). Next, to update the tree model as in G we follow Allesiardo et al. 2014) and estimate the gradient (0,) at O2 as:
((,)) = 2 p() (00(())) - (0,(()) eg.
((()) (1 11-0011100000 (O,(0)))
(8)
with sigmoid a and the ÿth basis vector denoted eg-
Regression setting: Here, the prediction is ÿ = 0 := 0,, and E' (0:) is a one-dimensional quantity which can be estimated using the loss loss/rewer reward value given for one prediction FFaxmman et al. 2005)
(fxxx) 8- E(D + 5u; x)u,
(9)
where is randomly sampled from {-1, +1}, and 8 0. Note that even with this simple estimator, Algorithm converges to good solutions with far fewer queries compared to baseline (Figure 3 scenarios when there is access to two-point feedback (Shamir 2017), we use (for small 8 > 0):
In
f'(O: x) = (25)-1 -e(g + 6;x) - E(D - -;)))
(10)
In our experiments (See Table 6), we find that this estimator performs competitive to the case when E is fully known (i.c., gradient is exact).
Choice of Prog. It important regularize the tree model as (a) it is overparameterized, and (b) we prefer sparse, shallow trees. Note that our model assumes a complete binary tree to begin with, thus regularization becomes key in order to learn sparse parameters in the nodes, which can be pruned if necessary doing a single pass, In our experiments, we use a combination of both L1 and L2 penalty on the weights.
5 Experiments
We evaluate our approach on the following aspects:
Performance on multi-class classification and regression benchmarks, compared to SOTA methods and standard baselines, in (a) supervised learning setting, and (b) bandit feedback setting.
2. Benefits of our design choices (in Section against standard existing techniques.
8

---

Published in Transactions on Machine Learning Research (09/2022)
Dataset
DGT (Alg.
TAO
LCN
TEL
PAT
Ridge
CART
AILERONS
1.72:0.016 (6)
1.76:0.02
2.211100068
2.0410.130
0.53=0.050
1.7510.000
2.01=00000
ABALONE
2.15::.0026 (6)
2.18:00.0
2.34::00066
2.38:10.203
2.3410.113
2.23:10.016
2.29=0.034
COMP-ACTIV
2.91=0.149 (6)
2.71=0.04
4.43=00498
5,2840.837
8.36+14427
10.05+0.506
3.35=0.221
PDDBIND
1.39:+0.017 (6)
1.45++0.007
1.39=00017
1.53+0.044
1.37=0.025
1.35+0.000
1.35=00000
CTSLICE
2.30+0.160 (10)
1.54+0.05
2.18+0.108
0.51
12.20=0.987
8.29+0.054
5.78=0.224
YEARPRED
9.05=00012 (8)
9.11++0.05
9.14+000355
9.53+0.079
9.90=0.043
9.50+00000
9.69=0.000
MICROSOFT
0.772=0.000 (8)
0.772100.000
0.77740.003
0.797
0.77910.000
0.771 000
YAHOO
0.795=0.001 (8)
0.79610.001
0.80410.002
0.889
0.80010.000
0.807=0.000
Table 1: Fully supervised (regression) setting: mean test RMSE. + std. deviation (over 10 runs with different random
seeds). Best height is indicated in parentheses for our method DGT (given in Appendix A.. For TEL, we set 7 = 0.01.
Dataset
DGT (Alg
TAO
LCN
TEL
CART
PROTEIN
67.80=0.40 (4)
68.41+0.27
07.52+0.80
67.63+0.61
57.53+0.00
PENDIGITS
96.3611.25
96.0810.34
93.26:10.84
91.6711.92
89.9410.34
SEGMENT
95.86=1.166
95.0110.86
92.79=1.35
92.1042.02
94.2311.86
SATIMAGE
06.64+0.95 (6)
87.4
84.22+1.13
84.65++1.18
84.18+0..00
SENSIT
83.67.0.223 (10)
82.52.0..5
82.02.10.77
83.60.1..16
78.31:10.00
CONNECT4
79.52+0.24 (8)
81.21+0.25
19.71+1.16
80.68=0.44
74.03=0.60
MNIST
94.0010.36 (8)
95.0510..16
88.90.10.63
90.9311.37
85.50110.06
LETTER
86,13.1.77 (10)
87.4110.41
66.34110.88
60.3513.81
70.13:10.00
FORESTCOVER
0..25+0050 (10)
83.27+0.32
67.13+33.00
73.47+0.83
77.85+00000
CENSUS1999
46.21 (8)
47.22+0.10
44.68-+0.45
37.95++1.95
46.40++0.00
HIV
0.712+0.020
0.627
0.738+0.014
0.562++0.000
BACE
0.767:10.045
0.734
0.791
0.81010.028
0.697:10.000
Table 2: Fully supervised setting: Comparison of tree learning methods on various classification datasets. Results are computed over 10 runs with different random seeds. Numbers in the first 10 rows are mean test accuracy (%) + std. deviation, and the last 2 rows are mean test AUC + std. deviation. For TEL, we set 7 = 0.01.
Datasets. We use all regression datasets from three recent. works: 3 large tabular datasets from Popov et al. (2020), chemical dataset from Lee and Jaakkola (2020) and 4 standard (UCT) datasets from Zharmagam- betov and Parreira-Perpinan (2020). For classification, we use 8 multi-class datasets from Carreira-Perpinaae and Tavallali (2018) and 2 large multi-class datasets from Féraud et al. (2016) which we report accuracy and 2 binary chemical datasets from Lee and Jaakkola (2020) where we follow their scheme and report AUC. Sizes, splits and other details for all the datasets are given in Appendix B
Implementation details. We implemented our algorithms in PyToh v1.7 with CUDA v112. We experi- mented with different quantizers (Rastegari et al. 2016: Courbariaux et al. 2016 Esser et al. 2020 for Sstep in (4), but they did not yield any substantial improvements, so we report results for the implementation given in Algorithm 2 For LCN (Lee and Jaakkola 2020), TEL (Hazimeh et al., 2020). and CBF (Féraud et al. 2016). we use their publicly available implement ations [LCN:TEN CBF). For TAO (Zharnagambe-
tov and Carreira- Carreira-Perpinan 2020 Carreira-Perpiiná and Tavallali 2018), , we did our best to implement their algorithrns in Python (using liblinear solver in scikit-learn) since the authors have not made their code avail- able yet (Zharmagambetor April 2021). For (linear) contextual- bandit algorithm with e-greedy exploration (Eqn. (6) and Algorithm in Bietti et al.] (2018)), we use TowpalWabbit (VW) with the --cb cc__explore and -epsilnn flags. We train CART and Ridge regression using scikit-learn. We tuned relevant pyreeepasameters validation sets (details in Appendix C.3). For all tree methods we vary h E 4,,4,6, 8, 10), (1) for LCN: optimizer, learning-rate rate, dropout, and hidden layers of ga; (2) for TAO: a regularization; (3) for DGT: momentum, regularization d1 X2 and overparameterization L, (4) for TEL: learning rate and regularization A2.
We report all metrics averaged over ten random runs, and statistical significance based on unpaired t-test at significance level of 0.05.
5.1 Supervised (tree) learning setting
In this setting, both the loss E as well as label information is given to the learner.
9

---

Published in Transactions on Machine Learning Research (09/2022)
1.1x
Relative Accuracy
Relative RMSE
1.6x
Comp-Activ (h 10)
YearPred (4 10)
1.0x
Ailerons (h: 66)
1.4x
0.9x
1.2x
SatImage (A
0.8x
Letter (A - 10)
1.0x
PenDigits (h
0.7x
1.0x
2.0x
4.0x 8.0x 16.0x
1.0x
2.0x
4.0x 8.0x 16.0x
Relative FLOPs
Relative FLOPs
DGT
-
y-L-y00
TEL y-1
Figure Performance vs. inference FLOPS (log scale) of the TEL method (for different 7 values that controls the number of leaves reached), relative to DGT, shown for the best performing heights for TEL on the respective datasets.
5.1.1 Regression
The goal is to a learn decision tree that minimizes the root mcan squared orror (RMSE) between the target and the predictions. Test RMSEs of the methods (for the best-performing heights) are given Table [ We consider three SOTA tree methods: (1) TEL, with 7 0.01 to ensure learning hard decision trees, (2) TAO (3) LCN, and baselines:
(4) parislla CART, (5) probabilistic tree with anncaling (PAT), discussed in the beginning of Section 3.3 and (6) linear regression ("Ridge)). We report nunbers from the TAO paper where available. DGT (with mini-batching in Appendix A performs better than both Ridge and CART baselines on almost all the datasets. On 3 datasets, DGT has lower RMSE (statistically significant) than TAO; on 2 datasets (COMP-ACTIV, CTSLICE), TAO outperforms ours, and on the remaining 3, they are statistically indistinguishable We clearly outperform L.CN on out of datasets, and are competitive on 3
5.1.2 Classification
Here, we wish to learn decision tree that minimizes misclassification error by training using cross-entropy loss. Test performance (accuracy or AUC as appropriate) of the methods (for the best-performing heights) are presented in Table 2 We compare against the same set of methods as used in regression, excluding PAT and linear regression. Of the 12 datasets studied, DGT achieves statistically siguificant improvement in performance on all but 1 dataset against CART, on 7 against LCN, and on against TAO. Against TAO, which is a SOTA method, our method performs better on datasets, worse on 5 datasets and on 4 datasets the difference is not statistically significant.
The non-greedy tree learning work of Norouzi et al. (015 reported results on 7 out of 12 datasets in their paper. What we could deduce from their figures (we do not have exact numbers) is that their method outperforms all our compared methods in Table 2 only on the LETTER dataset (where they achieve ~91% accuracy); on others, they are similar or worse. Similarly, the end-to-end tree learning work of Hehn et al. (2019) reports results on 4 out of 12 classification datasets. Again, deducing from their figures, we find their model performs similarly or worse on the datasets compared to DGT.
5.2 Comparison to soft trees, ensembles and trees with linear leaves
Soft/ Soft/Prott Proeabbrbbiiiiccc trees. DGT learns hard decision trees, with at most d h FLOPS per inference, as against soft httt/prbbabilistic trees with exponential (in h) inference FLOPS (e.g., PAT method of Table 1 without anncaling). In Tables [ and 2 we note that state-of-tho-art TEL method, with ? = 0.01 (to ensure that al most 1 or 2 leaves are reached per example), performs significantly worse than DGT almost datasets. We now look the trade-off between computational cost and performance of TEL, that uses a carcfully-designed activation function for predicates, instcad of the standard sigmoid used in probabilistic trees. The hyper-parameter 7 in TEL controls the softness of the tree, alfecting the nunber of leaves an
the
Despite efforts, LCN does converge on MICROSOFT dataset, while TEL docsn't converge on YAHOO and HIV (within the cut-off period of 48 hours)
4FLOPS: floating-poin operations
10

---

Published in Transactions on Machine Learning Research (09/2022)
Dataset
DGT
TEL (7 1)
TEL (7 = 0.1)
TEL (7 0.01)
PENDIGITS
96.36 + 0.25
96.54 + 0.46
95.10 1.23
86.09 2.53
SATIMAGE
86.64 + 0.95
87.64 + 1.23
84.92 + 0.94
84.12 + 1.20
LETTER
86.13 = 0.72
95.21 + 0.22
77.14 - 0.98
60.35 - 3.81
YEARPRED
9.05 0.012
8.99 0.067
9.14 + 0.055
9.56 = 0.081
AILERONS
1.72 + 0.016
1.75 + 0.062
1.85 + 0.089
2.05 = 0.013
COMP-ACTIV
2.91 0.149
2.80 0.205
3.60 1 0.564
5.12 1 0.863
Table 3: Performance comparison with soft trees on various classification and regression datasets. Results are computed over 10 runs with different random seeds. Numbers in the first rows are mean test accuracy (%) - std. deviation, and the last three rows are mean test RMSE + std. deviation. For TEL we show performance with different scttings y leading to different degrees of softness.
Dataset
DGT-Forest
XGBoost
AdaBoost
AILERONS
1.65 + 0.00 (6)
1.72 + 0.00 (7)
1.75 + 0,00 (15)
ABALONE
2.08 + 0.00 (8)
2.20 + 0.00 (10)
2.15 + 0.00 (10)
COMP-ACTIV
2.63 + 0.08 (8)
2.57 + 0.00 (10)
2.56 + 0.11 (10)
CTSLICE
1.22 + 0.07 (10)
1.18 + 0.00 (10)
1.31 + 0.01 (10)
YEARPRED
8.91 + 0.00 (8)
9.01 0.00 (10)
9.21 + 0.03 (15)
Table 4: Supervised tree ensembles: mean lest RMSE + std. deviation (over 10 rums with different random seeds) for forest methods regression datasets. DGT-Forest 30 trees while XGBoost and AdaBoost about 1000 trees. Maximum height of the trees is given in parentheses.
example lands in, and in turn, the inference FLOPS. In Figure 1 we show the relative performance (i.c. ratio of accuracy or RMSE of TEL to that DGT for a given height) vs relative FLOPS (i.c. ratio of mean inference FLOPP of TEL to that of DGT for a given height) of TEL, for different 7 values. First,, note that, by definition, DGT is (1,1) in the plots. When 7 0.01, TEL achieves about d h inference FLOPS on average, similar to that of hard decision tree (as in Table D. but its performance is significantly worse than DGT on all the datasets. On the other hand, TEL frequently outperforms DGT at = 1 (for instance, on SATIMAGE, it improves accuracy by 2%), but at significant computational cost (as much as 17x FLOPS over D We also present the performance comparison between DGT and TEL (at different settings) in Table Overall, DGT achieves competitive performance while keeping the inference cost minimal.
Tree ensembles. To put the results shown so far in perspective, we compare DGT to widely-used ensemble methods for supervised learning. To this end, we extend DGT to learn forests (DGT-Forest) using the bagging technique, where train fixed number of DGT tree models independently training data and aggregate the predictions of individual models (via voting or averaging) to generate prediction for the forest. We compare DGT-Forest with AdaBoost and XGBoost in Table First, expected, we see that DGT-Forest outperforms DGT (in Table I on all datasets. Next, DGT-Forest using only 30 trees outperforms the two tree ensemble methods that use as many as 1000 trees, on 3 out of 5 datasets, and is competitive the other 2. We also find that our results improve over other standard ensemble methods, on the same datasets and splits, published Zharmagambetov and Carreira-Perpinaal (2020).
bootstrap sample of the
Trees with lincar leaves. While DGT produces oblique trees whose leaves contain constant model (a learni constant value), we also compare it with trees containing linear model in the leaves. In general, tree with linear leaves is more expressive than tree of the same height with constant leaves present a comparison with such trees learnt by TAO. As expected, we see that these trees usually outperform those learnt by DGT.
0 In Table we
TEE still much better than standard probabilistic trees with 100x FLOPS for h 10. In the case classification, tree of height with linear leaves be equivalently represented by height O(K) +h, where K is the number of classes. For regression though, such equivalence does not hold.
11

---

Published in Transactions on Machine Learning Research (09/2022)
Dataset
DGT (with constant leaves)
TAO (with linear leaves)
ATLERONS
1.72 + 0.016
1.74 + 0.01
ABALONE
2.15 0.026
2.07 + 0.01
COMP-ACTIV
2.91 + 0.149
2.58 + 0.02
CTSLICE
2.30 + 0.166
1.16 1 0.02
YEARPRED
9.05 + 0.012
9.08 + 0.03
Table 5: Comparing DGT trees with constant leaves and TAO trees with linear model in the leaves. Scores are mean test RMSE + std. deviation (over 10 runs for DGT and over runs for TAO as reported in Zharmagambetor and Carreira- Perpinan (0200).
ForestCover
Mnist
SensiT
Census1990
80
40
Validation Aec
60
Validation Acc
Validation Acc
Validation Arc
80
-30
60
DGT- Bandd
40
20
20
20
10
eameedy (Liswar
87500 (#-uuries to f)
n x 62500 (#Queries to
8 x 31250 (s-Queries to
x 625000 (#*Queries to
Figure 2: Bandit feedback setting (classification one-point estimator in # #Queries to & vs mean accuracy on held-out set for multi-class datasets over 10 runs, with 95% confidence intervals. For DGT-Bandit, we use h for all datasets except CENSUS1990 where we use h = 8.
5.3 Bandit feedback setting
In the bandit setting, given a data point, we provide prediction using the tree function, and based on the loss for the prediction, we update the tree function. In particular, in this setting, neither the loss function nor the label information is available for the learner.
5.3.1 Classification
This is the standard contextual multi-armed bandit setting. and the e-greody contextual bandits algorithm (Bictti et al. 2018 with linear policy class. Many SOTA tree- learning methods (Carreira- Perpinán and Tavallali] 2018 Bertsimas et al. 2019) do not apply to the bandit setting, as their optimization requires access full loss function, to caaluate/updaate node parameters along different paths. For instance, standard extension of TAO would require evaluation of the loss function for given point O(2²) predictions. Similarly, directly extending non-greedy method of Norouzi et al. (2015) would require h + 1 queries to the loss on the same ezample per round, compared to DGT that can work with one loss function evaluation.
Here, we compare with CBF (Féraud et al. 2016)
Zharmagambetov and Carreira-Perpinan, 2020
Results. We are interested in the sample complexity of the methods, i.e., how many queries to the loss is needed for the regret become very small. In Figure 2 we show the convergence of accuracy against the #queries (n) to (0-1 loss) for DGT-Bandit (Algorithm D CBF (because their trees are axis-aligned, we use forests), and the e-greedy baseline, the large multi-clase class classification datasets. Each point the curve is the (mean) multi-class classification accuracy (and the shaded region corresponds to 95% confidence interval) computed on fized held-out set for the (trec) model obtained after rounds. It is clear that our method takes lar fewer examples lo converge to a fairly accurate solution in all the datasets shown. On FOresTCoVER with classes, after 10,000 queries (2% of train), our method achieves a test accuracy of 62.5% which only 16% worse compared to the best solution achieved using full supervision. On MNIST, CBF (with 25 trees) takes nearly 400K queries (~6.7 passes over train) to reach an accuracy of 80%, which DGT-Bandi reaches within 76K queries (~1.25 passes).
12

---

Published in Transactions on Machine Learning Research (09/2022)
Yahoo
Microsoft
YearPred
Abalone
Validation RMISE
1.6
Ridge
DGT-Bandh
Validation RMSE
1.2
Validation RMSE
80
Validation RMSE
60
6
1.2
1.0
60
1.0
20
0.8
2 875 (#Queries 4)
31250 Queries
31250 Queries
21875 (#Quueries
Figure 3: Bandit sotting (regression, one-point estimator in
9
J: #
Queries to vs RMSE on held-out set for regres-
sion datasets, averaged over 10 runs and 95% confidence intervals. Our method is run with defanlt hyperparameters
and
Dataset
DGT-Bandit (Alg.
Linear Regression
Squared
Huber
Squared
Huber
AILERONS
1.71#0.016
1.72:+0.016
1.78++0.003
1.87=00001
ABALONE
2.16:10.000
2.16:10.029
2.281100116
2.4410.078
CоMP- ACTIV
3.05++.119
2.99+0.166
10.05++0.412
10.27+0.202
PDRBIND
1.39+0.022
1.40=0.023
1.35 0.000
1.36+0.001
CTSLICE
2.36=0.212
2.42#0.168
8.32+00.51
8.52=0.042
YEARPRED
9.05=0.0113
9.06=0.008
9.54+0.002
9.68=0.003
MICROSOFT
0.772.0.000
0.773.10.001
0.78110.000
0.782100000
YAHOO
0.79610.001
0.79710.0002
0.81010.001
0.815110000
Table 6: Bandit setting (regression): Mean test RMSE + sld. deviation (over 10 runs with different random seeds) using two-point estimalor for E" in 10
5.3.2 Regression
We evaluate our method in this setting with two different losses (unknown the learner): (a) squared loss laq (0. (f- 2) and (b) the Huber loss defined as:
2 v)²
1
if 10 v
(0,
1
El -1 vl
- otherwise.
We use ridge regression with bandit feedback as a baseline (which is as good as any tree method in the fully supervised setting, Table 1 on 4 out of 8 datasets) in this setting, for which gradient estimation is well known (using perturbation techniques described in Section
Results. We are interested in the sample complexity of the methods, i.e., how many queries to the loss is needed for the regret to become very small In Figure 3 we show the convergence of RMSE against the # queries (n) to loss Eag for our method DGT-Bandit and the bascline (online) linear regression, both implemented using the one-point estimator for the derivative E' in (9. Each point on the curve the RMSE computed on a fired held-out set for the (tree) model obtained after n rounds (in Algorithm D Our solution takes far fewer examples converge to fairly accurate solution in all the datasets shown. For instance, the YAHOO dataset after 60,000 queries (13% of training data), our method achieves test. RMSE of 0.858 which is only 7% worse compared to the best solution achieved using full supervision (see Table 1
In Table G we show a comparison the mothods implemented using the two-point estimator in 10 on all the regression datasets, for two loss functions. Here, we present the final test RMSE achieved by the methods after convergence. Not surprisingly, we find that our solution indeed does consistently better on most of the datasets. What is particularly striking is that, on many datasets, the test RMSE nearly matches the corresponding numbers (in Table D in the fully supervised setting where the exact gradient is known!
5.4 Ablative Analysis
We empirically validate the key design choices of DGT motivated in Section B In all the cases, we vary only the aspect under study, fix all other implementation aspects to our proposed modeling choices, and report
13

---

Published in Transactions on Machine Learning Research (09/2022)
(a) Sum vs Prod. form 91
(b) Overparannelerrzatioonn
(c) Quantization vs Anneal
Dalaset
Prod, Equ. (2
Sum, Equ. [
L =
L ==3
+ Anneal
sign
AILFRONS
2.02+0.028
1.72+0.016
1.90+0.026
1.72+0.016
1.73++0002
1.72++0016
ABALONE
2.40=0.064
2.15:0.026
2,21+0.030
2.15:000026
2.31+0,06
2,1510.022 9.05+0.012
YEARPRED
9.72:10.063
9.05:000012
9.1810.017
9.05-10.012
9.1820.04
Table Ablation study of design choices in DGT (mean test RMSE std. deviation over 10 random seeds)
the performances the best (cross-validated) models.
1. Sum vs Product forms for paths. In our formulation, we use the sum form of path function qi as given in (4). We also evaluate the multiplicative form in 2 (used in PAT). Table 7 (a) shows that the product form has consistently worse (e-g-, over 17% in AILERONS) RMSF across the datasets than the ones trained with the sum form in our method. This indicates that our hypothesis about gradient ill-conditioning for the product form holds true.
Next, we study the benefit of learning a "deep embedding" for 2. Effect of Overparameterization
data points via multiple, linear, fully-connected layers as described in Section 3.2 It is not clear a priori why such "spurious" linear layers can help at all, as the hypothesis space remains the same. But, we find supportive evidence from Table 7 (b) that adding just layers helps improve the performance in many datasets. On YEARPRED, overparametorization makes the difference between SOTA methods and ours. Recent findings (Arora et al. 2018) suggest that linear overparameterization helps optimization via acceleration. We find that modest value of = 3 works across datasets. We defer thorough study of this aspect and its implications to future work.
3. Quantization vs Anncaling. Finally, we study the offectiveness of the quantized gradient updates, i.e. using the sign function the forward pass, and the straight-through estimator compute its gradient in the backward pass. We compare against the annealing technique for scaled sigmoid function (a(a) I+exp(-s-a)> i.., slowly increasing the value of during training. Table 7 (c) suggests that the quantized updates are crucial for DGT; on ABALONE, annealing performs worse than all the methods Table except PAT which improves over because of overparameterization and the use of sum form.
6 Conclusions
We proposed an end-to-end gradient-based method for learning hard decision trees that admits dense up- dates to all tree parameters. DGT enables learning trees in several practical scenarios, such as supervised learning and online learning with limited feedback. Our comprehensive experiments in the supervised set- ting demonstrated that DGT achieves nearly SOTA performance on several datasets. On the other hand, in the bandit setting, where most existing techniques do not even apply, DGT yields accurate solutions with low sample complexity, and in many cases, matches the performance of our oflline-trained models. In experiments, default hyperparaneters worked well (sce Appendix C.3 but it is unclear how to set them in real-world online deployments where dataset characteristics might be significantly different. We plan to explore relevant approaches from parameter-free online learning literature (Chap. 9, Orabona (2019)). Understanding linear overparameterization, extending quantization techniques to learning trees with higher out-degree, and deploying DGT ML-driven systems that need accurate, low cost models, are potential directions at this point.
14

---

Published in Transactions on Machine Learning Research (09/2022)
References
Contextual bandit forests http:://www...accaaeeeeeeo/oooos
Forest_ for the Coeteotttetaall...aaaaaaaaa Bandit Conteextua_Bandtt_Proboeeee
Locally-constant networks (LCN). http:///tss/ttttooooo////aaaaaaa
Tree Ensemble Layer.
trees
Vowpal Wabbit. http:://roppallaaiit.orr
Alckh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi- point bandit feedback. COLT, pages 28 Citeseer, 2010.
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pages 1638-1648 2014.
7. Allen-Zhu, Yi,, and Y Liang. Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers. In Advances in Newral Information Processing Systems, 2019.
Robin Allesiardo, Raphaäl Férand, and Djallel Bouneffouf. A neural networks committee for the contextual bandit problem. In The 21st International Conference on Neural Information Processing, pages 374-381, 2014.
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. In International Conference on Machine Learning, pages 244-253, PMLR, 2018
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322 332. PMLR, 2019.
Randall Balestricro. Neural dccision trees. arXiv preprint arXim:1702.07330 2017.
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint urXiv:1308.4438 2013.
Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning, 106(7):1039 1082, 2017.
Dimitris Bertsimas, Jack Dunn, and Nishanth Mundru. Optimal prescriptive trees. INFORMS Journal on Optimization, 1(2):164-183, 2019.
Gérard Biau, Erwan Scornet, and Johannes Welbl. Neural random forests. Sankhya A, 81(2):347 386, 2019.
Alberto Bietti, Alekh Agarwal, and John Langford. A contextual bandit bake-off. arXiv preprint AKXi:1802.0406, 2018.
Loo Breiman, Jerome Friedman, Charles J Stone, and Richard A Olshen. Classification and regression trees. CRC press, 1984.
Miguel A Carreira-Perpaa Perpinán and Pooya Tavallali. Alternating optinization of decision lrees, with application to learning sparse oblique trees. In Advances in Neural Information Processing Systems, pages 1211-1221,
2018.
Matthieu Courbariaux, Itay Hubara, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio. Binarized neural networks: 'raining deep neural networks with weights and activations constrained to +1 -1, ar preprint XrXiv:1602, 02830, 2016.
Varsha Dani, Thomas Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. 21st. Annual Conference Learning Theory, 2008.
15

---

Published in Transactions on Machine Learning Research (09/2022)
Ariyam Das, Jin Wang, Sahil M Gandhi, Jac Lee, Wei Wang, and Carlo Zaniolo. Learn smart with less: Building better online decision trees with fewer training examples. In IJCAT, pages 2209-2215, 2019.
Thomas G Dietterich, Richard H Lathrop, and Tomás Lozano-Pérez. Solving the multiple instance problem with axis-parallel rectangles. Artificial intelligence, 89(1-2)311-11, 1997.
Pedro Domingos and Geoff Hulten. Mining high-speed data streams. In Proceedings of the sioth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 71-80, 2000.
Miroslav Dudík, John Langford, and Lihong Li. Doubly robust policy evaluation and learning. In Proceedings of the 28th International Conference on International Conference on Machine Learning, ICML'11, page 1097 1104, 2011.
Adam N. Elmachtoub, Ryan McNellis, Sechan Oh, and Marck Petrik. A practical method for solving contextual bandit problems using decision trees. UAI, 2017.
Steven K. Esser, Jeffrey L. McKinstry, Deepika Bablani, Rathinakumar Appuswamy, and Dharmendra S. Modha. Learned step size quantization. In International Conference Learning Representalions, 2020.
Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without gradient. In Proceedings of the sirteenth annual ACM-STAM Symposium on Discrete Algorithms, pages 385 394, 2005.
Jerome Friedman, Trevor Hastie, Robert Tibshirani, et al. The elements of statistical learning, volume
Springer series in statisties New York, 2001.
Nicholas Frosst and Geoffrey Hinton. Distilling a neural network into a soft decision tree. arXie preprint 17X.:1711.097844 2017.
Raphaël Féraud, Robin Allesiardo, Tanguy Urvoy, and Fabrice Clérot. Random forest for the contextual bandit. problem. In Arthur Gretton and Christian C. Robert, editors, Proceedings of the 19th Interna- tional Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages 93-101, Cadiz, Spain, 09-11 11 May 2016. PMLR.
Henry Gouk, Bernhard Pfahringer, and Eibe Frank. Stochastic gradient trees. In Proceedings of The Eleventh Asian Conference on Machine Learning, volume 101 of Proceedings of Machine Learning Research, pages 1094 1109. PMLR, 2019.
Husscin Hazimeh, Natalia Ponomareva, Petros Mol, Zhenyu Tan, and Rahul Mazumder. The tree ensemble layer: Differentiability meets conditional compulation. In Hal Daumé III and Aarti Singh, editors, Pro- ceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 4138 4148. PMLR, 13 18 Jul 2020. URL httpp::/pproceeding.. mlr. .tres// p119/hazimeh2aa.hae html
Thomas M Hehn, Julian FP Kooij, and Fred A Hamprecht. End-to-end learning of decision trees and forests. International Journal of Computer Vision, pages 1-15, 2019.
Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El- Yaniv, and Yoshua Bengio. Binarized neural networks. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 4114-4122. Citescer, 2016.
Ozan Irsoy, Olcay Taner Yıldız, and Ethem Alpaydm. Soft decision trees. In Proceedings of the 21st International Conference on Pattern Recognition (ICPR2012), pages 1819-1822. IEEE, 2012.
Ruoming Jin and Gagan Agrawal. Efficient decision tree construction on streaming data. In Proceedings of the ninth ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pages 571 116,576,200 2003.
Michael I Jordan and Robert A Jacobs. Hierarchical mixtures of experts and the EM algorithm. Neural computation, 6(2):181-22) -24,, 1994.
16

---

Published in Transactions on Machine Learning Research (09/2022)
Cijo Jose, Prasoon Goyal, Parv Aggrwal, and Manik Varma. Local deep kernel learning for efficient non-lineas sym prediction. In International Conference on Machine Learning, pages 486-494. PMLR, 2013.
Peter Kontschieder, Madalina Fiterau, Antonio Criminisi, and Samuel Rota Bulo. Deep neural decision forests. In Proceedings of the IEEE International Conference Computer Vision, pages 1467-1475, 2015,
Ashish Kumar, Saurabh Goyal, and Manik Varma. Resource--fficient machine learning in 2KB RAM for the internet of things. In Proceedings of the 34th International Conference on Machine Learning, pages 1935-1944. JMLR. org, 2017.
Guang-He Lee and Tommi S. Jaakkola. Locally constant networks. In International Conference on Learning Representations (ICLR), 2020.
Chaitanya Manapragada, Geoffrey 1 Webb, and Mahsa Salehi. Extremely fast decision tree. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Dala Mining, pages 1953 1962, 2018.
Mohammad Norouzi, Maxwell Collins, Matthew Johnson, David J Fleet, and Pushmeet Kohli. Efficient non-greedy optimization of decision trees. In Advances Newral Information Processing Systems, pages 1729 1737, 2015.
Francesco Orabona. A modern introduction to online learning. arXiv preprint 1xxi:11912.13113 2019.
Sergei Popov, Stanislav Morozov, and Artem Babenko. Neural oblivious decision ensembles for deep learning on tabular data. In International Conference on Learning Representations, 2020.
Ross Quinlan. C4. 5: Programs for Machine Learning. Elsevier, 2014.
Mohammad Rastegari, Vicente Ordonez, Joseph Redmon, and Ali Farhadi. XNOR-Net: ImageNet classifi- cation using binary convolutional neural networks. In ECCV, 2016.
Karthik Abinav Sankararaman, Soham De, Zheng Xu, W Ronny Huang, and Tom Goldstein. The im- pact. of neural network overparameterivation on gradient confusion and stochastic gradient descent. Tn International Conference on Machine Learning, pages 8469 8479. PMLR, 2020.
Ishwar Krishnan Sethi. Entropy nets: from decision trees to neural networks. Proceedings of the IEEE, 78 (10):1605 1613, 1990.
Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. The Journal of Machine Learning Research, 18(1):1003-1113, 2017.
D. Sieling. Minimization of decision trees is hard to approximate. In 18th IEEE Annual Conference on Computational Complexity, 2003. Proceedings., pages 84 92, 2003. doi: 10.1109 /0tp//CCC.000..1444004 1214112
Ryutaro Tanno, Kai Arulkumaran, Daniel Alexander, Antonio Criminisi, and Aditya Nori. Adaptive neural trees. In International Conference on Machine Learning, pages 6166-6175. PMLR, 2019.
Jesper E Van Engelen and Holger Hoos. A survey on semi-supervised learning. Machine Learning, 109 (2):373 440, 2020.
Zhenqin Wu, Bharath Ramsundar, Evan N. Feinborg, Joseph Gomes, Caleb Geniesse, Ancesh S. Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learning. Chem. Sci., 9:513-58 530, 2018. doi: D..1039CCSCC0266G URL http:://xx......// doi. wtt.oo/o.////////.....oo
Yongxin Yang, Trene Garcia Morillo, and Timothy M Hospedales. Deep neural decision trees. arXie preprinl arXiv:1806.066: 069888, 2018.
Valentina Zantedeschi, Matt Kusner, and Vlad Niculae. Learning binary decision trees by argmin differen- tiation. In Marina Meila and Tong Zhang, oditors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 12298-12309 PMLR, 18 24 Jul 2021.
17

---

Published in Transactions on Machine Learning Research (09/2022)
Arman Zharmagambetov. Email communication, April 2021.
Arman Zharmagambetov and Miguel Peareira-Perpinant Smaller, more accurate regression forests using tree alternating optimization. In Proceedings of the 37th International Conference on Machine Learning, pages 11398-11 1188-11408 11408, 2020.
18

---

Published in Transactions on Machine Learning Research (09/2022)
A Tree Learning Algorithm Variants
Our method DGT for learning docision trees in the standard supervised learning sctting is given in Algo- rithin 3 Note that here we know the loss function & exactly, so compuling the gradient is straight-forward (in Step 9). Also, the dot product in Step 9 (as well as in Steps 11 and 12 of Algorithm [ is appropriately defined when K > 1, as it involves a vector and a tensor. The back propagation procedure, which used both in DGT and in DGT-Bande (Algorithm 1 is given in Algorithm 2 K = case, for clarity).
Algorithm 3 DGT: Learning decision trees in the supervised learning (batch) setting
Input: training data (x,, M=) height h, max epochs Tmax; learning rate 77, loss E, regularization (A, O Preg), overparameeteriaation L, hidden dim di, [4]
2: Output: Tree model: W, and @ E R22*
Init: w E Rd xd w E Rdaxd, ,..... w E -1e-d Og randomly.
x, x;; 1] for ...,..., // incorporate bias
for epoch 1 < < Tmax do
(W, )) = 0-)1)
7:
for each mini-batch B do // perform SGD mini-batches
8:
0, = f(x;; W, θ), iE B (via 2 and hard a in 3 // Compute the tree model prediction
(Wwo) Vel)
Ve Ve. Ev,, 01) BackProp(xx; W. O) // Algorithm 2
10:
((m) t (m)) V W(m) l - N V Win a Preg( (W, O), for m = 1.2..... ...L.
11:
θ - θ - Vo - Vo reg (.W)
12:
r, O+) = O)
13:
return W Tiax
B Datasets Description
Whenever possible use the train-test split provided with the dataset. In cases where a separate validation split is not provided, we split training dataset in 0.8 0.2 proportion to create validation. When splits are provided, we create five random splits of the dataset and report the mean test scores across those splits, following Zharnagambetov and Carreira-Perpinae (2020). Unless otherwise specified, we normalize the input features to have mean 0 and standard deviation for all datasets. Additionally, for regression datasets, we min-max normalize the target to [0, 1].
B.1 Regression datasets
We used eight scalar regression datasets comprised of the union of datasets used in Popov et al. (2020) Lee and Jaakkola 2020 Zharmagambetov and Parrinna 2020 Table summarizes the dataset details.
AILERONS: Given attributes describing the status of the aircraft, predict the command given to its ailerons.
Given aliribules deecciiing physical measurements, predict the age of an abalone. We encode the categorical ("sex") attribute as one-hot.
ABALONE:
COMP-ACTIV Given different system measurements, predict the portion of time that CPUs run in user mode. Copyright notice can be found here: http:/ http://www.cc. www.ww.toroooo..co.o.o delve/copyrriht..nott
CTSLICE Given attributes as histogram features (in polar space) of the Computer Tomography (CT) slice, predict the relative location of the image on the axial axis (in the range |0 180]).
19

---

Published in Transactions on Machine Learning Research (09/2022)
PDBBIND
Given
standard "grid features' (fingerprints of pairs
between lig-
and and protein:
see Wu et al. (2018)), predict binding affinities. MIT License
http::::/githuu.co/// deepchem seeepcchmm/eepchenn deepchem httpichhem//bb/////eee http//blobbbaaeaeee http//mattterrt///// LICENSE..
YEARPRED Given several song coatistics/metaddaat (timbre average, timbre covariance, etc.), pre- dict the age of the song. This is subset of the UCI Million Songs dataset.
MICROSOFT Given 136-dimensional feature vectors extracted from query-url pairs, predict the relevance judgment labels which take values from 0 (irrelevant) to (perfectly relevant).
YAноo Given 699-dimensional feature vectors from query-url pairs, predict relevance values from
4.
B.2
Classification datasets
We use eight multi-class classification datasets from Carreira-Peryee Perpinán and Tavallali (2018), two multi-class classification datasets from Féraud et al. (0016) and two binary classification datasets from from Lee and Jaakkola (2020). Table summarizes the datasct details.
PROTEIN Given features extracted from amino acid sequences, prodict sccondary structure for protein sequence.
PENDIGITS Given integer attributes of pen-basee handwritten digits, predict the digit.
SECMENT: Given 19 attributes for each 3x3 pixel grid of instances drawn randomly from a database of 7 outdoor colour images, predict segmentation of the central pixel.
SATIMAGE Given multi-spectral values of pixels in 3x3 neighbourhoods in satellite image, predict the central pixel in each neighbourhood.
SENSIT Given 100 relevant sensor features, classify the vehicles.
CONNECT4: Given legal positions in a game connect-4, predict the game theoretical outcome for the first player.
MNIST: Given 784 pixels in handwritten digit images, predict the actual digit.
LETTER Given 16 attributes obtained from stimulus observed from handwritten letters, classify the actual letters.
FORESTCOVER Given 54 cartographic variables of wilderness areas, classify forest cover type.
CENSUS1990 Given 68 attributes obtained from US 1990 census, classify the Yearsch column.
HIV Given standard
Morgan fingerprints (2,048
binary MIT
indica-
tors of chemical substructures). predict HIV replication. (https://gt)
License
blob/ master LICENSE..
BACE Given standard Morgan fingerprints (2,048 binary indicators of chemi- cal substructures), predict binding results for a set of inhibitors. MIT License
C
Evaluation Details and Additional Results
All scores are computed over 10 runs, differing in the random initialization done, except for TAO on re- gression datasets which uses runs. In all the experiments, for a fixed tree height and datasct, our DGT implementation takes 20 minutes for training (and < hour inchuding syper-paramete search over four GPUs.)
20

---

Published in Transactions on Machine Learning Research (09/2022)
Table Classification datasets description
dataset
# features
# classes
train size
splits (tr.valitest)
# shuffles
source
CONNECT4
126
43,236
0.64 0.16 0.2
1
LIBSVM
MNIST
780
10
48,000
Default
1
LIBSVM
PROTEIN
357
14,895
Default
1
LIBSVM²
SENSIT
100
63,058
D
1
LIBSVM?
LETTER
16
26
10,500
Defaul
1
LIBSVM
PENDIGITS
16
10
5,995
Default
1
LIBSVM²
SATIMAGE
36
3,104
Default
LIBSVM
SEGMENT
19
1,478
0.64 0.16 0.2
LIBSVM
FORESTCOVER
54
371,846
0.64 0.16 0.2
UCP
CENSUS1990
68
18
1,573,301
0.64 0.16 0.2
UC1
BACE
2,048
1,210
Default
MolcculeNet
HIV
2,048
2
32,901
Default
1
MoleculeNet
Table Regression datasets description
dataset
# features
train size
splits (tr:valites))
# shuffles
source
AILERONS
40
5,723
D
LIAC 10
ABALONE
10
2,004
0.5 0.1 0.4
UCI
COMP-ACTIV
21
3,932
0.5 0.1 0.4
Delve UC1 8.6
CTSLICE
384
34,240
0.5: 0.1 0.4
PDBBIND
2,052
9,013
Default
MoleculeNer UC
YEARPRED
90
370,972
Default
MICROSOFT
136
578,729
Default
MSLR-WEL WEB10K
YAUOO
699
473,134
Default
Yahoo Music Ratings
C.1 Height-wise results for the fully supervised setting
Heightwise results for our method DGT and compared methods on various regression and classification datasets can be found in Fig. and Fig. respectively. As mentioned in Section 5.1 we find that the
Dataset
DGT (Alg.
TAO
LCN
TEL
CART
PROTEIN
67.80+0.40 (4)
68.41-0.27
67.52+0.80
67.63+0.61
57.53+0.00
PENDIGITS
96.36+0.255 (8)
96.08-10.34
93.26++0.44
94.67+1.92
89.94+0.34
SECMENT
95.86+1.16
95.01+0.86
92.79+1.35
92.10+2.02
94.23+0.86
SATIMAGE
86.64+0.95 (6)
87.41+0.33
84.22+1.13
84.65+1.18
84.18+0.30
SENSIT
83.6710.23 (10)
82.5240.15
82.02:1.777
83.6010.16
78.3110.00
CONNECT4
79.5240.24 (8)
81.21110.5
79.71+1.16
80.6810.44
74.03 0.60
MNIST
94.0010.36 (8)
95.05-0.16
88.90110.63
90.93++1.7
85.59=0.06
LETTER
86.13:1.72 (10)
87.41=0.41
66.3410.88
60.3543.81
70.13+0.08
CORESTCOVER
70.25 (10)
83.27=0.32
67.13+3.00
73.4740.83
77.85+0.00
CENSUS1990
16.2140.17 (8)
47.22=0.10
44.68++0.45
37.95++195
46.40=0.00
HIV
0.712-0.000
0.627-0.000
0..011
0.562-10.000
BACE
0.76740.045
0.734
0.791
0.81011.002
0.697-10.000
Table 10: Fully supervised setting: Comparison of tree learning methods various classification datasets. Results are computed over 10 runs with different random seeds. Numbers the first 10 rows are mean test accuracy (%) + std. deviation, and the last. 2
test AUC +: std. deviation. For TEL, we 7 0.01.
21

---

Published in Transactions on Machine Learning Research (09/2022)
numbers obtained from our implementation of TAO Zharmagambetor and PerreiaaaPerpian 2020) differ from their reported numbers on some datasets; we quote numbers directly from their paper in Table 1 where available. Keeping up with that, in Figure we present height-wise results for the TAO method only on the 3 datasets that they do not report results on. We do not present heightwise results for TEL as we find that the method generally poor across heights when we restrict, y to be small (~ 0.01).
C.2 Sparsity of learned tree models
Though we learn complete binary trees, we find that the added regularization renders lot of the nodes in the learned trees expendable, and therefore can be pruned. For instance, out of 63 internal nodes in height 6 AILERONS tree (best model), only 47 nodes receive at least one training point. Similarly, for height 8 YahOo tree (best model), only 109 nodes out of total 255 nodes receive at least one training point. These examples indicate that the trees learned by our method can be compressed substantially.
Table 11: Hyperparameter selection for our method: we use default values for many, and cross-validated over the given sets for the last
HYPERPARAMETER
DEFACLT VALUE or RANGE
OPTIMIZER
RMSprop
LEARNING RATE
le-2
LEARNING RATE SCHEDULER
CosineLR Scheduler (3 restarts)
GRADIENT CLIPPING
le-2
MINI-BATCH SIZE
128
EPOCHS
30-400 (depending on dataset size)
OVEREARAMETERRIATTON (L)
[1,3} (hidden dimensions in Table 12
REGULARIZATION (A1 OR Ag
{5e-5, 1e-5, 5e-6, 1e-6, 0} > else
MOMENTUM
(0, 0.3) if regression else {0, 0.3, 0.8}
C.3 Implementation details
C.3.1
Offline/batch setting
DGT We implement the quantization and arg max operations in PyTorch as autograd functions. Below, we give details of hyperparameter choices for any given height. (h E (2, 4, 6, 10))-
We train using RMSProp optimizer with learning-rate 1e-2 and cosine scheduler with 3 restarts; gradient clipping 1e-2; momentum of optimizer {0, 0.3} for regression and {0, 0.3, 0.8} for classification; regulariza- tion Å1, A2 E (5e-5, le-5, 5e-6, 1e-6, 0}; and overparameterization L E [1,3) with hidden space dimensions given Table 12 We use a mini-batch size of 128 and train our model for 30-400 epochs based on the size of dataset. Table II summarizes the choices for all the hyperparameters. Note that we use default values for most of the hyperparameteers, and cross- vals-va only few.
Table 12: Hidden dimensions for overparameterization (L 3): we use a fixed set of d,'s for a given height h; note ds 2h
HEIGHT
HIDDEN DIMENSIONS
2
[240, 240, 3)
4
[600, 600, 15]
6
[1008, 1008, 63)
8
[1530, 1530, 255]
10
[2046, 2046, 1023]
22

---

using the bagging Published in Transactions on Machine Learning Research (09/2022)
DGT-Forest We extend DGT to learn forests (DGT-Forest, presented in Section 5.2 technique, where we train a fixed number of DGT tree models independently training data and aggregate the predictions of individual models (via averaging for regression and voting for classification) to generate a prodiction for the forest. The number of tree models trained is set to 30. The sample of training data used to train each tree model generated by randomly sampling with replacement from the original training set. The sample size for each tree relative to the full training set is chosen from {0.7, 0.85, 0.9, Hyperparameteess for the individual tree models are chosen as given previously for DGT, with the following exceptions: momentum of optimizer E {0, 0.3, 0.4, 0.6} and regularization is used even when 1.
bootstrap sample of the
We implemented TAQ in Python since the authors have not made the code available yet (Zhar- magambetov April 2021). For optimization over a node, we use scikit-learn's LogisticRegression with the liblinear solver For the classification datasets, we initialize the tree with CART (trained using scikit-leam) mentioned in Carreira-Perpinan and Tavallali (2018), train for 40 iterations, where for the LogisticRe- gression learner, we set maxiter= 20, tol= 5e-2 and cross-validate X1 E {1e-4, 1c-3, 1e-2, 1,-1,1, 10, 30). The results we obtain are close to/narginally better than that inferred from the figures in the supplementary material of PCrrreira-Perpinna and Tavallali (0018).
TAO
For the regression datasets we initialize the predicates in the tree randomly as mentioned in Zharmagambetor
and Perpinan ) For PDBBIND, we initialize the leaves randomly in [0. 1), train for 40 iterations, set maxiter 20, tol = 5e-2 and cross- validate X E {le-3, 1e-2, 1e-1, 1]. For the large datasets, MICROSOFT and YAHOO, we initialize all leaves to 1, train for 20 iterations with maxiter = 20, tol = 1e-2 and cross- validate À E {1e-3, 1e-2, 1e-1}. In all cases, post-training, as done by the authors, we prune the tree to remove nodes which don't receive any training data points. For the other regression datasets, despite our efforts, we weren't 't able to reproduce the reported numbers, so we have not provided height-wise results for those (in Figure
LCN We use the publicly available implementation of LCN provided by the authors. On all classifi- cation and regression datasets we the algorithm for 100 epochs, using batch size of 128 (except for the large datasets YEARPRED, MICROSOFT and YAΠОO where we use 512) and cross validate on: two optimizers Adam (AMSGrad variant) and SGD (Nesterov momentum factor 0.9 with learning rate halv- ing every 20 epochs); learning rate E fle-5, 1e-4, 3e-4, 1e-3, 3e-3, 1e-2, 3e-2, 3e-1,3e-11, 1}; dropout probability E 0.25. 0.5, 0.75]; number of hidden layers in 9o E {0, 1, 2, 3,4, 4,5) 5} and between the model at the end of training vs. the best performing early-stopped model. On HIVand PDBBIND we were able to improve on their reported scores.
TEL We use the publicly available implementation TEL We use the Adam optimizer with mini-batch size of 128 and cross-validate learning rate E fle-5, 1e-,, 1e-3, le-2, le-1}. X2 e {0, 1e-8, 1e-6, 1e-4, 1e-3, le-2, 1e-1, 1,0, 1003. The choice of 7 E (1e4,,1e33, 1e-2, 1e-1, is explicitly spec- ified in Section 5 when we present the results for this method. To compute the (mean relative) FLOPS, we measure the number of nodes encountered by their model during inference for each test example, and compute the average.
Thttps:/ Stttps://wwrrd www.w/le..tt..dd.....
http://lhwmttoo//dtttttttttt multeettttsm/tiilsssss... html We use The provided train-test splits; in rase a separate valiriation datasel is not provided we split train in ratio 0.8 0.2
"Wu et al. (2018)
https:/ www.ww.w.. fe..f.pp..ppppp. Itorgo/Regressee Regression/////eeeeeeeeeeogeeiee SaciiooonnDae DataSets. html
Splltt and shuffles obtaied from Zharmagambeton and Carreira-
Carreira-Perpinan Perpinan 2020
14 *hhtpp:///e htttp://www.ce es toronto. edu/ delve data, /wopppaatti/ddss....oeooo
hhtpps:/ hacch/ve/rccveeeeeee ics uci edu ml/ datascts, phpp)
hitpp:: /www www.mmmcctoooooooooommo com /nn-us/ research. jetojecct/sssy
httpss//www.mmccroof..comm
httpsss/wweaccopesandboo yahoo. com catalog. hhtpppppppppaaa (dstatype=r
we do not use and La regularization simultaneously
17The solver dousn't allow learning when all data points belong to the same cluss. While in many cases this scenario isn't encountered, for MICROSOrT and YA8Oо make the solver learn by augmenting the node-local training set D with ( x,, 3i)
some i, where (xi.1)
18
23

---

Published in Transactions on Machine Learning Research (09/2022)
PAT and ablations For the probabilistic annealed tree model (presented in Table well in Ta- ble (c)), we use sigmoid activation the predicates and softmax activation after the AND layer. We tune the annealing of the softmax activation function with both linear and logarithmic schedules over the [10,0000000110100000,,,,01111
ranges
Additionally we tune momentum of optimizer. We follow similar annealing schedules quantization ablation as well but use additive AND layer and over- parameterization instead.
CART We the CART implementation that is part of the scikit-learn Python library. We cross-validated min_samples_leas leaf over values sampled between 2 and 150.
Ridge We use the Ridge implementation that is part of the scikit-learn Python library. We cross-validated the regularization parameter over 16 values between 1e-6 and 5e-1.
C.3.2 Online/bandie setting
In the online/ /baddi classification setting, do not perform any dataset dependent hyperparameter luning for any of the methods. Instead try to pick hyperparameter configurations that work consistently well across the datasets.
DGT-Bandit For the classification setting we remove gradient clipping and learning rate scheduler. We further restrict to L = 1, A = 0, X = 0, momentum = 0 (and mini-batch size = 1, by virtue of the online setting and accumulate gradient over four steps). We use the learning rale and å parameter which work consistently across all datasets. For the classification case we
(exploration probability Eqn. 7 0.3 and ó parameter Eqn. (10) and Eqn. (9) to 0.5. Learning rate 1e-3 used. For the regression setting only tune the learning rate (1e-2,le-), 8 E (100500100.0550010000000 and momentum of optimizer.
Linear Regression We implemented linear regression for the bandit feedback setup in PyTorch. We use RMSprop optimizer and we tune the learning rate E {1e-2, 1e-3), momentum {0, 0.4, 0.8), regularization E (1, 0., 0,1, 0.05, 0.01). We use number of epochs similar to our method. To compute the gradient estimate, we vary (in Equ. (9] {1, 0.1, 0.05, 0.01, 0.0013.
e-rreedy (Linear) For linear contextual-bandit algorithm with e-greedy exploration (Equation and Algorithm 2 Bietti al. (2018)), we use VowpalWabbit (VW) with the -cb _eb_exlorreeeee and -epsilon flags. We tune learning rate f0.001, 0.01, 0.1, and the probability of exploration E {0.01, 0.1,,..1,..33 0.5}. We use 77 0.01, 0.5 which work well across all the datasets.
We use the official implementation provided by the authors (CFF) and use the default hyperparam- eter configuration for all datasets. Since their method works with only binary features, we convert the catogorical features into binary feature vectors and discretize the continuous features into 5 bins, following their work (Féraud et al. 2016).
CBF
24

---

Published in Transactions on Machine Learning Research (09/2022)
Abalone
CtSlice
Comp-Activ
Ailerons
15.0
9.0
DGT-Labeled
2.6
RMSB
2.5
RMSE
12.5
10.0
RMSE
7.5
2.7
LCN
CART
2.4
6.0
2-4
7.5
5.0
4.5
2.2
2.5
1.8
2
10
height (h)
height (h)
height (h)
height (h)
PdbBind
Microsoft
Yahoo
YearPred
0.795
0.870
10.2
0.790
RMSE
1.55
RMSE
0.785
RMSE
0.8.40
RMSSE
9.9
1.50
0.780
0.825
0.6
1.45
0.775
0.810
9.3
1.40
0.770
0.795
9.0,
2
10
8
10
2
10
8
10
height (h))
height
hoight
height
Figure 4: Mean Test RMSE (over 10 random seeds) of competing methods vs tree height for regression datasets. We do not show the performance of TAO method some datasets (see Sections 5.1 and C.1b LCN did not converge MICROSOFT (see Section 5.1
Connect4
Protcin
Letter
Mnist
86
80
90
100
72
74
Accuracy
77
Accuracy
Accuracy
58
Accuracy
73
56
CART
48
LCN
65
40
10
20
TAD
8
10
2
6
10
height (l)
height (1)
helght (N)
height (h)
SensiT
Sogment
Satimago
PenDigits
100
100
90
100
92
84
82
84
Accuracy
Accuracy
Accuracy
Accuracy
84
68
74:
68
76
52
66
68
58
60
20
50
20
10
8
10
2
4
10
6
8
10
height (h)
height
height (h.
height
(h)
Consus 1990
HIV
Bace
Forest
45
0.72
0.82
82
Accuracy
RMSE
AUC
0.64
0.74
74
0..56
0.68
88
.35
0.58
0.40
0.50
50
8 10
2
6
10
10
height (h)
height (h)
height (h)
height (h)
Figure 5: Mean (%) Test Accuracy or Test AUC of competing methods (over 10 random seeds) tree height for classification datasets.
25


Reviews:
[{"review_id": "0kEesfo1Mb", "reviewer": "Reviewer_HdAq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths.   \nThe proposed method looks interesting and reasonable. Experiments are extensive with many datasets and baselines. \n\n\nWeaknesses.   \n(1) I feel like the paper can be decomposed into two separate parts: the first one is about using the straight-through estimator to handle the “hard” step functions, the second one is how to estimate the gradient for the bandit-feedback setting.    \n(2) It would be better if the authors could elaborate on why they want to focus on the bandit-feedback setting rather than the traditional supervised setting. I think the motivation should be made more clear.   \n(3) The techniques (e.g., straight-through and gradient estimation) used in this paper are simply taken from existing papers. The novelty of this paper is limited in this sense.    \n(4) The structure of the paper can be improved. For example, Algorithm 2 seems to be integral to understanding Algorithm 1. But Algorithm 2 is put to appendix, making the main paper not self-contained.    \n(5) Background about bandit should be more complete. The current terminology regarding bandit is confusing: contextual bandit setting, bandit feedback, online optimization, black-box loss function. These concepts are related but certainly not the same. For example, contextual bandit is defined as the multi-armed bandit setting where we have a contextual vector available at each round, whereas bandit feedback is when we can only get the partial feedback regarding the loss of the current state. The bandit feedback is also applied to non-contextual bandit setting. I think it’s better if the authors could have a background section to focus on bandit related concepts.\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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a learning method for decision trees without softening the trees. This paper considers both the traditional supervised learning and bandit-feedback setting.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Add a background section to clarify    \n(1) the motivation about why the bandit setting is focused    \n(2) related concepts about the bandit.", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "bF5qL4MtXD", "reviewer": "Reviewer_tDsy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n- The paper is overall well-structured and easy-to-follow.\n\n- The arguments in the main paper overall make sense to me.\n\n**Weaknesses**\n\n- I think the experiments for the bandit feedback setting is a bit confusing. Some of my questions are listed below.\n  - The authors evaluate the different methods based on \"the accuracy/RMSE computed on a fixed held-out set for the model obtained after n rounds\". This is very different from the average regret defined in Section 2, and in essence closer to \"best-arm identification\". At least for classification problems, is it possible to include bandit algorithms designed for best-arm identification? That looks like a more reasonable comparison.\n  - The benchmark policy is $\\epsilon$-greedy with linear policies. Is it possible to compare $\\epsilon$-greedy with more complicated policy classes? The inferior performances of $\\epsilon$-greedy with linear may be only because the linear class is too small to characterize the true model; besides, these $\\epsilon$-greedy curves converge much faster.\n  - Please specify the $\\epsilon$ used in the experiments for $\\epsilon$-greedy. Also, what's the impact of choosing different $\\epsilon$'s?", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors consider the problem of learning hard decision trees (where each input example lands in a single leaf) with bandit feedback. Key contributions include:\n\n- They re-formulate the tree learning problem such that 1) the multiplicative form is rewritten as sums so as to control ill-conditioned gradients; 2) the additions of deep linear layers are allowed.\n\n- They propose a new algorithm to solve the proposed formulation. The algorithm uses quantized gradient descent.\n\n- They conduct experiments in both supervised learning settings and bandit settings. In the supervised setting, the empirical performance is roughly comparable to TAO. In the bandit setting, the proposed algorithm outputs a more accurate model faster than basic benchmarks.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "- (Particularly Critical) Please address the concerns regarding the bandit experiments raised in \"weaknesses\".\n\n- (Critical) To handle bandit feedback in the classification setting, the gradient (8) is computed based on the arm-sampling scheme specified in (7). Does that mean we have to use $\\epsilon$-greedy type of algorithms? Can we use more sophisticated bandit algorithms there? Please clarify.\n\n- (Critical) In Section 3.2, the authors only discuss linear layers. However, based on my knowledge, many often-used layers are not linear, and I don't think the current method can be easily extended. Can authors discuss how limited this assumption is? I'm fine if extensions can't be made, but I would like the authors to at least acknowledge it.\n\n- Please define \"FLOPS\" in Section 5.2.\n", "broader_impact_concerns": "No.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8Ndxwb0HyO", "reviewer": "Reviewer_fNzK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I will evaluate Strengths And Weaknesses based on claims made in the submission and whether those claims are supported by \"accurate, convincing and clear evidence\" as per reviewer guidelines. \n\nClaims that are supported:\n- \"enabling sample-efficient tree learning in online, bandit feedback setting without exact information on the loss function or labels.\" The method is indeed efficient to apply in bandit setting. \n- \"easily extensible to ensembles that outperform widely-used choices by practitioners.\" The claim is well-supported experimentally. In terms of methodology, it also makes sense as ensembling trees is relatively straightforward to perform.\n\nClaims that are not supported or weakly supported:\n- \"Novel, unified, differentiable solution for learning decision trees accurately for practical and standard evaluation settings\". I do have some concerns regarding novelty. I think that the method is a variation of soft decision trees with some trivial modifications: \"and\"->\"or\"gradients, straight-through gradient estimation which is commonly practiced in quantization literature, etc. I don't mind of re-phrasing this as \"novel variation of soft decision trees\" or smth similar.\n- logarithmic inference cost. Although, this is true for tree part, but over-parameterization adds additional cost which makes the method less \"logarithmic\" per say compared to conventional CART trees. In order to obtain a strong support for this claim, I'd suggest adding model sizes. This is partially done in fig.1 but only for the inference time and for DGT vs TEL. How about other approaches? CART, TAO? I assume their inference time is faster (especially given the over-parameterization of the proposed method)? I'd suggest adding a proper comparison of model sizes (including inference time) for all models.  \n- \"competitive or superior performance compared to SOTA tree learning methods on a variety of datasets, across different problem settings...\" Although I appreciate for including extensive evaluation of the proposed approach, I think that some critical baselines are missing. For instance, since authors use over-parameterization, I think it would be fair to include more advanced baselines which also applies feature transformations (e.g. Kontschieder et al. 2015, Tanno et al. 2019 but with similar model sizes); or TAO with linear leaves? Or maybe report the results with/without over-parameterization?\n- \"significantly more accurate and sample-efficient than general methods for online settings\". I'm not sure what does \"general methods for online setting\" means exactly, but assuming that soft-trees are considered as such, I don't think that this claim is validated without addressing the previous comment. Moreover, I'd not consider the difference between TEL as \"significant\" (also why TEL is missing for YAHOO?).", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces DGT, dense gradient trees, a variation of soft tree learning algorithm. Assuming the initial tree structure is fixed (complete tree) with random parameters at each node, the learning is done via SGD as follows:\n- During forward propagation, a tree is considered as hard and only the most probable path is followed per instance;\n- As for the backward pass, the tree is considered as soft where gradients of the step function are computed via \"straight-through\" estimation. \n\nThe method is generically applicable to supervised problems such as regression and classification, but the authors also provide extension for Bandit setting where reward/loss function is not explicitly given (but can be computed). Applying SGD for supervised problems is straightforward, whereas in Bandit setting authors use a simple finite difference approximation of derivatives.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "see the previous section. In general, I find that the paper will be interesting and beneficial for some individuals in TMLR's audience and thus, I consider accepting this manuscript if: either claims are reformulated and/or additional experiments/metrics are added based on my comments.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is definitely an interesting work which, while drawing from several known ideas, successively synthesizes them into the new, widely applicable method that uses hard trees in order to achieve state-of-the-art performance in general and performance superior to SOTA in the bandit setting. Extensive empirical evaluations comparing against many state-of-the-art methods attests to the competitiveness/superiority of DGT. All the reviewers support the acceptance of the paper. This work is a welcome contribution to TMLR. Congratulations!

I still would like to suggest some very minor revisions (a few of them involve typos):
- p1, second paragraph: "Bandit setting" —> "The bandit setting"
- p2, first line "supervised setting" —> "the supervised setting"
throughout the paper: it is better to write out "wrt" as "with respect to"
- p2, last paragraph before Related Work: "in online, bandit feedback setting" —> "in the online, bandit feedback setting"
- I believe your "Related Work" header is written as \\paragraph{}, and this doesn't work because (to my eyes) the subsequent headers "Non-greedy techniques:", etc. are also written as \\paragraph{} (meaning that they are not interpreted as belonging to the "Related Work" section. You should be able to come up with a fix for this.
- p2, paragraph before "Non-greedy techniques:": "Most relevant ones" —> "The most relevant ones"
- p2 and p3: "backprop" —> "backpropagation" (to be consistent with other instances where you did write "backpropagation"
- p3: "mixed ILP" —> "mixed integer linear program (ILP)"  
- p3: "The recently proposed Zantedeschi et al. (2021)" —> "The recently proposed (Zantedeschi et al., 2021)" 
- p3: "that yields \\emph{small} number" —> "that yields a \\emph{small} number"
- p3, "Bandit feedback:": "learns axis-aligned decision tree/forest" —> "learns an axis-aligned decision tree/forest"
- p3: Just before the math display prior to (1) (and again in the sentence before (1)), when you define $\\ell$ using $\\mapsto$, I do not think this is the correct use of $\\mapsto$. The RHS of $\\mapsto$ is usually a value, not the range (output space) of the function. I cannot suggest an easy fix but you might see one.
- p3, the second before equation (1): You should be careful in writing $\\{x_i, y_i\\}_{i=1}^n$ as the training data is not a set (the same example can appear multiple times). 

Using $(x_i, y_i)_{i=1}^n$ 
would be better as the training "set" is in fact a sequence.
- be consistent on "overparameterization" vs "over-parameterization"
- There is a typo in the line immediately below Algorithm 1 where you define the sigmoid function: "$\\exp(-s . a)$" perhaps should be "$\\exp(-s \\cdot a)$" ?
- At the end of equation (8), second line, you have a double comma ", ,"
- I noticed that you refer to $L$ as "overparameterization". Perhaps you can clarify this use of the term to refer to $L$ when you first introduce $L$, as it is not that intuitive (it feels more natural to refer $L$ as the number of [hidden] layers)
- In footnote 2, it is not clear what is meant by "cut-off period"; how long was this period?
- In Figure 1 (left), there should be a way to fix the figure/legend so that the legend doesn't invade the curves being plotted!
- In the definition of Huber loss, I believe you are missing a factor of 1/2 in the first case (should be $\\frac{1}{2} (\\hat{y} - y)^2$ if $|\\hat{y} - y| \\leq \\xi$)
- Of course this is up to you, but it would look better if your figures were vector graphics (save as eps or pdf using matplotlib or ggplot etc.)
Decision: Accept (poster)