Differentiable Decision Tree via "ReLU+Argmin" Reformulation
Authors: Qiangqiang Mao
Jiayang Ren
Yixiu Wang
Chenxuanyin Zou
Jingjing Zheng
Yankai Cao
Venue: NeurIPS 2025 spotlight ()
Keywords: Differentiable decision tree
"ReLU+Argmin''-based hard tree
ReLU-based hard splits
Oblique decision tree
Gradient-based optimization
Primary area: general_machine_learning

Abstract: Decision tree, despite its unmatched interpretability and lightweight structure, faces two key issues that limit its broader applicability: non-differentiability and low testing accuracy. 
This study addresses these issues by developing a differentiable oblique tree that optimizes the entire tree using gradient-based optimization. We propose an exact reformulation of hard-split trees based on "ReLU+Argmin" mechanism, and then cast the reformulated tree training as an unconstrained optimization task. 
The ReLU-based sample branching, expressed as exact-zero or non-zero values, preserve a unique decision path, in contrast to soft decision trees with probabilistic routing. The subsequent Argmin operation identifies the unique zero-violation path, enabling deterministic predictions. 
For effective gradient flow, we approximate Argmin behaviors by scaling softmin function. To ameliorate numerical instability, we propose a warm-start annealing scheme that solves multiple optimization tasks with increasingly accurate approximations. 
This reformulation alongside distributed GPU parallelism offers strong scalability, supporting 12-depth tree even on million-scale datasets where most baselines fail. 
Extensive experiments demonstrate that our optimized tree achieves a superior testing accuracy against 14 baselines, including an average improvement of 7.54\% over CART.

Differentiable Decision Tree via "ReLU+Argmin" Reformulation
Qiangqiang Mao, Jiayang Ren, Yixiu Wang, Chenxuanyin Zou, Jingjing Zheng, Yankai Cao" University of British Columbia, Vancouver, Canada
Abstract
Decision tree, despite its unmatched interpretability and lightweight structure, faces two key issues that limit its broader applicability: non-differentiabiliy and low testing accuracy. This study addresses these issues by developing differen- tiable oblique tree that optimizes the entire tree using gradient-based optimization. We propose an exact reformulation of hard-split trees based on "ReLU+Argmin" mechanism, and then cast the reformulated tree training an unconstrained op- timization task. The ReLU-based sample branching, expressed as exact-zero non-zero values, preserve unique decision path, in contrast to soft decision trees with probabilistic routing. The subsequent Argmin operation identifies the unique zero-violation path, enabling deterministic predictions. For effective gradient flow, we approximate Argmin behaviors by scaling softmin function. To ameliorate nu- merical instability, we propose warm-start annealing scheme that solves multiple optimization tasks with increasingly accurate approximations. This reformulation alongside distributed GPU parallelism offers strong scalability, supporting 12-depth tree even million-scall datasets where most baselines fail. Extensive experi- ments demonstrate that our optimized tree achieves a superior testing accuracy against 14 baselines, including an average improvement of 7.54% over CART.
Introduction
Decision trees have attracted significant attention in machine learning primarily due to their inter- pretability and lightweight structures. Their strength lies in transparent "IF-THEN" rules, making them ideal for tasks requiring clear recision-making processes. However, their practical use is often limited by the lower test accuracy, forcing a shift towards other models that sacrifice interpretability advantages. Another limitation the non-differentiabiiityy which severely restricts their gradient- based applications, especially when embedded in optimization tasks. For instance, in reinforcement learning, decision trees offer an interpretable alternative neural networks policy representation; yet, non-differenttabiliyy remains major barrier [Vos and Verwer 2024 Marton et al.) 2025].
Aiming for higher accuracy and fewer parameters, oblique decision tree, pivot extension of classic orthogonal tree, holds great potential. Oblique tree uses linear feature combination for hyperplane splits. When data distribution follows hyperplane boundaries. tends to generate smaller trees with higher accuracy [Costa and Pedreira] 2023]. Nevertheless, inducing oblique trees is challenging, owing innumerable linear combinations at each node [Zhu al. 2020 Earlier works focus on optimizing splits at an individual node using greedy algorithms like CART-LC [Breiman et al. 1984 and DC1 (Murthy et al. 1994]. Alternative methods rely on greedy orthogonal CART to induce oblique trees by rotating feature space, exemplified by HHCART (Wickramarachchi et al.) 2013) and RandCART Blaser and Fryzlewicz) 2016). Despite their advancements, such greedy methods may be suboptimal due to weaker splits at subsequent nodes. To avoid this, non-greedy approach TAO (Zharnagambetov and Carreira-Perpinan 2020 optimizes a subset of nodes each step. Considering optimizing all
"Corresponding author; yankai.cam cataaiica@@aa. ubc.ca.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

nodes, [Bertsimas and Dunn [ presents optimal tree to formulate tree training as mixed-intege programming (MIP). Besides, sparse optimal trees (Lin et al. 2022] complements MIP-based work by considering sparsity. However, these methods often face scalability issues, especially for oblique tree with expanded search space. Recent efforts in optimal oblique tree [Boutilier et af.) 2023 Zhu et 20200 have been confined to classification tasks with limited categorical predictions. In contrast, regression tasks with infinite continuous outputs remain challenging. In response, the originators of MIP-based work propose local search alternative ORT-LS (Dunn, 2018 for tasks that are unsolvable by MIP. However, ORT-LS still suffers from high computational cost and suboptimal accuracy.
To significantly improve computational tractability compared to those MIP formulations, in this work, we reformulate entire tree training as an unconstrained optimization task. Our reformulation makes it easily solvable via gradient-based tools and also facilitates adapting it into a differentiable tree. The classic tree's non-Lifferentiability mainly arises from two sources of hard decisions: hard splits at branch nodes that determine sample branching, and the unique decision path that assign each sample to a specific leaf node for sample prediction. Given the non- di--deffeeeniibiiitty of hard decisions, two intuitive solutions have been used: treating the gradient via straight-through estimators (STE) like DGT [Karthikeyan et al. 2022], GradTree [Marton et al. 2023] and DTSemNet regression tree [andd et al.] 2024]. J. and approximating binary decisions (0 or 1) with continuous probabilities in (0.1) using soft approximations like sigmoid function in soft trees [issy et al. 2012 Wan et al. |021 Frosst and Hinton 2017) and other soft variants like smooth- step functions in TEL [Hazimeh et al. 2020]. However, STE may neglect critical gradient information, resulting in suboptimal learning. as evidenced by results reported in the original work of (Marton et al. 2023). where their method underperforms CART on 17 of 36 datasets (their Tables and 2), as well as in our own experiments. Regarding soft approximations, previous efforts predominantly construct "soft" decision trees with soft splits, probabilistic path and predictions. Nonetheless, there do exist scenarios where a hard split or decision is not only appropriate but also imperative, as in Appendix A Besides, other gradient- based trees exist, but they might not preserve classic tree structures or be exact reformulations, such as DNDT (Yang et al. 2018) which uses Kronecker products for class predictions, and the method by
Norouzi et al. [015 which uses a surrogate loss. Due to their differences in structure, formulation and optimization, we consider them complementary work suited for distinct application scenarios.
To retain the two sources of hard decisions, we propose a "ReLU+ Aargmnn--maaasstt -based exact reformulation. ReLU functions enforce hard decisions to direct samples left or right, and quantify violations of the correct directions that a sample must follow to reach its unique leaf. Our ReL.Ubbased splits, in sharp contrast soft splits with left-right probability, yield hard (exact-zero or non-zero) decisions for sample branching. This leverages ReLU's property of producing distinct zero and non-zero values True-False decision boundaries. Such a property has ever been used implicitly mimic a decision tree using neural networks [Le and Jaakkola 2020]. in contrast to our direct application for reformulating and optimizing tree. Next, the correct decision path is identified as the unique path with zero cumulative violations. This can be easily formulated via Argmin operation over zero and non-zero (positive) values. To avoid undefined gradient in Argmin, we approximate with a scaled softmin function. Noticeably, two clarifications are necessary: first, our Argmin is a mathematical operation over discrete set, and should not be confused with "Argmin Differentiation" or "Implicit Differentiation" [Gould et al.] 2016). The latter is used in LatenTree (Zantedeschi et al.) 2021], which frames tree training as a relaxed MIP problem within bilevel optimization setting. However, their work is not directly related to our unconstrained task, and unrelated to approximate the Argmin operation itself. Second, our softmin approximation is introduced purely to facilitate gradient backpropagation during training; at the inference phase, our method reverts to using Argmin for deterministic behavior. This technique of using approximation during training while reverting to original function during inference was previously used in the work of [Mao and Cao 2024].
Arrgmin
First, we propose a "ReLU+Argmin" -based exact reformulation for hard- split trees, avoiding softness introduced in sample branching and predictions. Second, we cast the entire tree training as an unconstrained optimization task, introducing a scaled softmin function to approximate Argmin behaviors for effective gradient flow. Third, to balance approximation degree with numerical instabilities, we present a strategy of multi-run warm start annealing to progressively refine solutions. Fourth, our implementation supports multi-GPU acceleration, significantly enhancing scalability. Finally, we provide an extensible
Our Contributions:
-based Differentiable Decision Tree optimization framework (termed RADDT) for inducing both regression trees and classification trees. The source code is available in httph:tt////gtt //gith////tub////// wtw.//oo./miiiee comm/YankaiCrruu//AADD
2

---

Experiments mainly focus on regression tasks across 17 medium- scale datasets and 7 million-scale datasets, showing our competitive testing accuracy as well as strong scalability, To enable a more convincing comparison, additional evaluations on the same datasets used in the original work of certain compared baselines further highlight the superiority of our method.
Performance:
Our optimized trees outperform the compared decision trees in testing accuracy. Notably, it outperforms CART by 7. 7.54%, local search ORT-LS by 3.72%, and gradient-based LatentTree by 6.24%, and DGT by 2.66% on average.
Our trees with linear predictions impressively outperforms tree ensembles, including random forest by 2.01% %, XGBoost by 1.12% and gradient-brrg based TEL by 0.76%.
Our method successfully scales to 12-depth deep tree on million- scale datasets, where existing gradient- based trees like GradTree, SoftDt, DGT and LatentTree fail.
2 Foundations of Oblique Decision Tree
We explore oblique decision trees from an optimization perspective by formulating tree training as an optimization problem for both regression and classification tasks. For case of understanding, we follow the notation for optimal binary trees as used in the original work of Bertsimas and Dunn [2177]. Consider a dataset {It, y4 J with imput Ø; E [0, 1]", and output values y/: E [0, 1| for regression and Y/i E (1,.... e} for classification with classes. A binary tree of depth D comprises T 2 1 nodes, where each node is indexed by t E T = [1,.... .TT in a breadth- first order. The nodes can be categorized into two types: branch nodes, which execute branching tests and are denoted by E TB [1,
[T/2]] }. and leaf nodes denoted by t E Т,, {[T/2] 1,.... TT,. responsible for leaf predictions. Each branch node comprises a split weight a, E IP and a split threshold b, E R to conduct a branching test (af 0; < by) for samples allocated to that particular branch node. If sample æ; passes the branching test, it is directed to the left child node at index 2/; otherwise, to the right at index +1. Each leaf node contains 8, provide prediction value specific to the current leaf, which varies depending on the task. For classification, 0: = [ie E R. and the prediction for a sample e; assigned to leaf t is y, h₁ For regression, 0, [k; R' h, E IR,, which considers two types of leaf prediction: linear and constant prediction. Specifically, tree with linear predictions involves linear feature combination [Quinlan [998], with general form of Vi = k. æ; + h4. Tree with constant predictions a special case of linear predictions, where K remains zero. It is the most commonly used type in existing decision tree methods, with y h, The training of oblique trees involves solving the following optimization problem:
min E (yi, 9:) A,b,9
(1a)
s.t. Js = ftree (A, 2;), i (1....,n.
(1b)
where Stree is the decision tree model, {.) is square error loss for regression and cross entropy loss for classification. A = {a),... ([T/2]) } and b = (b,,a.,,b are tree split parameters,
0 = [0(//2++1, 3 is leaf prediction parameter.
3
Unconstrained Optimization Reformulation for Oblique Tree Training
We first propose an exact reformulation of decision trees and further cast the training as uncon- strained task, allowing for gradient-based optimization for improved solvability and accuracy.
3.1 "ReLU++rgmin""- -based exact reformulation for hard-split decision trees
ReLU-based hard splits and carrectly-diretted path formulation (no softness at branch nodes for sample branching): A sample x; correctly assigned to a leaf node by following a sequence of left-right decisions at its ancestor nodes. The ancestor nodes set A, consists of left Ai, and right A ancestors, traversed via left and right branch, respectively. such that A, A. UJ AT. For left ancestor node j E AL, æ, must pass the branching test a² x;; < by to be directed to the left, whereas for right j E AT, it must fail the test proceed right. To formulate these left-right hard decisions for æ; we use ReLU functions to characterize the violation of correct direction at each node j. termed u.y:
ReLU (a. ---b by). j A ReLU (b, x1) jE EA.
Uj.j =
(2)
3

---

where Vi.j = 0 indicates that z; follows the correct direction, i.c. left for A4 and right for A while Vi.j * 0 is a violation of correct direction. These deterministic ReLU-based zero and non-zero values eliminate the softness in sample branching, opposed to soft approximations with continuous probabilities (0,1) at each branch node. The cumulative violations across all branch nodes are:
USe - Σ Viij
(3)
jEA,
JEAT
where U = indicates x; follows all correct directions to leaf node t; otherwise U,, * 0(> 0) corresponds to the overall violations of correct sample assignments.
Unique decision path formulation using Argmin (no softness at leaf nodes for sample prediction): Since z; follows a unique decision path to a specific leaf node, only one leaf node holds a violation- free path. Such a unique zero U.. removes the softness in sample assignment and prediction, in contrast to soft approximations with probabilistic paths for predictions. The unique path can be easily formulated by Argmin function (more concretely, one-hot encoded Argmin Mi) applied to Uz.:
M (U,,s) 1 (t (Argmin(U,) + (T/21)),
where U, (U J. M- (-) is the one-hot encoding of the result of Argmin operation. only outputting one at leaf node i with U.. = O; otherwise outputting zero
For clearer understanding of our reformulations, a 2-depth tree example is provided in Figure 1 To be correctly assigned to leaf node 5, the sample must pass the branching test at nodes I with af æ; S bj to be directed left, which implies that ReLU (a x;; b1) O. The sample also needs fail at node The corresponding violations are f4,1 = 0 and 04 = 0, leading to unique zero-violation path with USS = U4 + 1/22- For other leaf nodes, the total violations are non-zero (positive). The unique MI (Ui.)) = 1 indicates 2; is correctly assigned to leaf 5.
be directed right with an mi > b2 which implies that ReLU (b2 a æ;) O.
sollmess deterministic zero or notr-zero violation
4u Re1U (ut
=0
Assigned leaf mode 1-
RoLU (b. af
[1) (2)
No softness leaf nodes
unique decision path by zero U.,
U. 0 Ug 15.1 + U2.2
U.o 4 Argmin (anc-hot encoded Argmin)
U.r
Figure 1: Illustrative example for a unique path 1 + 2 + 5 of "ReLU+Arrmin' "-baaa bbssed hard tree.
3.2 Unconstrained optimization for RReLUtArgmiin--aae tree training
Next, we reformulated-tree training as unconstrained optimization task with objective L as:
Σ M (U.e)) E ()).
(5)
EET,
Differentiability analysis of ReLU and Argmin: The trainable variables A, b, O are expressed in V.j and U2.,, where ReLU and Argmin are involved. The gradient behavior at ReI.U(O) has been extensively studied and is considered theoretically negligible, though numerical effects may arise due to float-point precision [Bertoin et al. [021]] Consistent with this, we treat it as inconsequential for gradient-based optimization, as evidenced by the success of ReLU networks [Leonardi and Spallanzani 2020). Regarding Argmin, avoid undefined gradient flow at certain points, we use scaled softmin function to approximate Argmin behaviors in Equation (4).
Scaled softmin to approximate Argmin:
Scaled softmin $ (.) is applied to U., by Equation (6). Under extreme scaling, softmin ensures that veruevalued US. approaches one; otherwise to zero. The scale factor plays a critical balance between approximation accuracy and optimization stability. Regarding a selection, larger a yields closer approximation, but may cause numerical insta- bility, potentially compromising optimization capabilities. Further empirical analyses are given in Appendix B Identifying optimal a that balances approximation degree and differentiability remains challenge. To mitigate this, we propose annealing strategy in Section 4.1 for a better trade-off. (-())))))
8 (U,,)) Σiere (aa-)
(6)

---

Notably, this softmin operation is used only during training to facilitate gradient backpropagation. In inference, is deterministically recalculated for yi, as described in Appendix [c] More importandy, does not introduce softness into sample branching and prediction, as the zaluevalued ReLU outputs and violation-fret free path described in Section 3.1 are established prior to the approximation step.
Following Equation
(6)
we redefine the optimization task C in Equation 7
13
L
Σ
s (Ui,) 8 (1s.
DETL
4
Differentiable Tree Training via Gradient-based Entire Tree Optimization
Our reformulated task in Equation 7 closely approximates non-differentiable training problem, which can be efficiently solved by our proposed entire tree optimization framework.
4.1 Multi-run warm start annealing strategy for scaling softmin operations
Regarding the challenge of selecting an optimal earlier discussed for Equation (6. propose
strategy of multi-run warm start annealing to refine solutions through multiple optimization tasks with increasingly accurate approximations. The annealing has been used (Hehn and Hamprecht/ 2017] Karthikeyan et al., 2022 [ee and Jaakkola [220] to balance the trade-off, though not specifically for our application softmin. However, their annealing is typically applied within single training run, such as changing a every few epochs, which may affect stable gradient updates. In contrast, our annealing operates across multiple runs. The solution from an optimization task with smaller is used to warm-start the next task with a larger a. By starting with a smaller a and gradually increasing it, this enhances approximation accuracy, while mitigating numerical instability associated with larger a. Detailed steps including sampling of scaled factors {a1,- an } are given in Appendix D and the implementation is integrated within our tree optimization framework, Appendix [ Algorithm [ For the a selection, although binary search provides a structured way to explore different a values by evaluating the performance at the midpoint and adjusting a boundaries accordingly, still involves
testing isolated a values without leveraging the solutions from previous a trials. Our subsequent ablation study shows that gradually increasing a, rather than a fixed large value, leads to better
training outcomes. We detail binary search comparison in Appendix D
4.2 Influence of initial values and their adjustments for gradient-based optimization
good initialization is crucial. Since softmin operates on U1. which summarizes ReL.U-based violations that are either zero or non-zero, samples near decision boundaries (a? x; by 0) may yield non-zero but near-zero violations. An illustration is given in Appendix E While such near-zer zero violations do not affect Argmin behaviors, which only select the unique path with U.. = O, they can sensitively affect softmin. Specifically, softmin may fail to ideally produce a value close to one, reducing approximation accuracy. bad initial solution for A and b can result in poor optimization outcome. To mitigate this, A and b can be adjusted to maximize the margin between the decision boundary and nearest samples, without altering existing sample assignments as illustrated by green line in Appendix D. Figure 3 This adjustment can be easily achieved either by calculating the median of a. x, for the closest samples on both sides of the boundary, or using support vector machine to binary classification task with explanations in Appendix [
treat sample assignments
Noticeably, this strategy mainly handles cases where z² 1ixz-00 bb; z 0. However, it becomes ineffective in the corner case where a;- O and by O with same violations for all leaves. This limitation can impair optimization. To mitigate this, we typically incorporate this strategy with multiple random initializations. Fortunately, our extensive experiments show that such corner cases appear to be extremely rare in practice, and we have not observed noticeable performance degradation.
4.3 Differentiable decision tree optimization framework
Unlike greedy methods that optimize each node sequentially, our approach concurrently optimizes the entire tree, including A and b all branch nodes and all leaf nodes. Our "Rel Arggminn- based Differentiable Decision Tree (termed RADDT), outlined in Appendix G Algorithm begins at
5

---

multiple random initialization (Line + 1-D. This increases the chance of finding better solutions. Each initialization is adjusted to achieve the maximum margin (Line For each start, the optimization with our annealing is conducted to produce tree candidate (Tine 0 75 The final optimal tree selected by comparing candidates from multiple starts, with each evaluated using deterministic leaf predictions and exact loss calculations without approximation (Linee -7)) This framework
is readily implementable using existing tools like PyTorch. Despite the introduction of additional hyperparameters in gradient-based optimization, tuning them is not typically necessary because their effects are straightforward. More empirical analyses are detailed in Appendix F
Numerical Experiments and Discussions
We mainly evaluate regression tasks, but also include the same classification datasets used by certain baselines for more convincing comparison. Our tree with constant or linear predictions, termed the respective RADDT and RADDT-Linear, compared against a broad range of trees in testing accuracy, training optimality and training time. The 14 baselines include: (a) greedy CART, HHCART, RandCART, and OC1; (b) non -oneeredyy TAO (Zhrmmagambetov and Carreira-Perpinate
2020 ; (c) gradient-
trees using STE like GradTree [Marton et al. 2023). DGT [Krthhkkyan al. [022] and DTSemNet
[Panda et al. 2024] ; (d) sigmoid-base
soft tree SoftDT Frosst and Hinton| [017]] (e) relaxed
MIP-based tree solved via implicit differentiation LatentTree (Zantedeschi et al. 2021 (f) local
search ORT-LS Dunn 2018 (g) soft tree variant using smooth-step function TEL Hazimeh et al.,
2020] (Tree ensemble); (h) other ensembles like random forest RF and XGBoost. Our primary focus is on comparing oblique trees. The inclusion of orthogonal CART serves as a foundational work, aligning with prior work on oblique trees, such TAO, DGT, DTSemNet and TEL, which also use CART for comparison. Although outperforming CART is an expected outcome, its inclusion helps quantify the amount of improvements achievable by oblique tree. GradTree included to enable a fair comparison against other STE- based oblique trees like DGT and DTSemNet. Since it remains uncertain whether oblique trees can match tree ensemble's accuracy, we include RF and XGBoost as a commonly used and strong ensemble baselines, and TEL as the oblique ensemble counterpart.
These 14 baseline comparisons
conducted across four groups of datasets: (i) 17 medium-sized regression datasets with fewer than 41k samples (primary focus); (ii) 27 classification and 9 regression datasets used in the papers of certain baselines (for more credible comparison); (iii) 4 wooldw datasets with about 100 samples, and 3 synthetic datasets with 5000 samples (for comparing global optimality with global tree ORT-MIP [Bertsimas and Dunn| 2017] and known ground truth); (iv) 7 large-scale datasets each with at least million samples (for evaluating scalability).
Detailed dataset information and usage are given in Appendix H Comparisons focus accuracy in Coefficient of Determination (usually denoted as R²), and computational time in seconds. The Friedman Rank (Sheskin 2020] is also used to statistically sort the compared methods according to their testing accuracy, with a lower value indicating better performance. Comprehensive details on the implementation for each compared method, and computing facilities are given in Appendix]]
5.1 Testing accuracy comparison
To evaluate the testing accuracy of our optimized tree, we compare it against diverse decision trees and tree ensembles with different tree induction methods. For a fair comparison, we conduct depth tuning for all tree methods to select the optimal tree depth from 1 to 12 (except for CART from I to 100 due its tendency to rely deeper depth for higher accuracy).
Comparison against other decision trees: In Table I our RADDT consistently outperforms compared trees in test accuracy across Group (i) 17 datasets. Specifically, RADDT surpasses the foundational CART by 7.54%, greedy HHCART by 5.64%, and ORT-LS by 3.72%. These results underscore the effectiveness of our tree optimization. Besides, Friedman rank comparisons reinforce these findings, with RADDT attaining the highest rank. Detailed results for each dataset are provided in Appendix K.T
Regarding existing gradient-based based trees, since DGT and LatentTree fail to scale to depth 12, we evaluate them under another fixed-depth setting in Section 5.22 GradTree, as observed in Table [] performs poorly in our experiments. This result is within our expectations, as their original paper reports that GradTree underperforms CART on out of 36 datasets (see their Table and 2 in [Marton et al. 2023).. Nonetheless, to ensure more credible comparison, we further evaluate our

---

Table Test accuracy for compared decision trees on 17 medium-sized datasets in Group (i).
Greedy Methods
(iradient-based
Local Search
Ours
CART
RandCART
HRCART
DC1
GradTree
SoftDT
CRT LS
BADDT
Testing Accuracy (It", %)
74,85
71.20
76.75
73.31
64,30
72.72
78.67
82.39
Tree Deppth
10.24
8.12
8.29
8.12
10.29
10.29
6.24
7.29
Friedman Rank
4.65
5.88
3.65
5.06
7.00
4.76
3.24
1.76
Other two gradient- DCT and LatentTree are compured in Table with fixed depths due scalability issues at depth 12.
MMor credible results on their originally- dataset are discussed below, include GradTree, SoftDT, DGT, and DTSemNet.
method the same classification datasets used in their study. Similar same-dataset comparisons are also conducted for SoftDT, DGT-Linear, DTSemNet and non non-greedy TAO-Linear as below.
A more credible same-dataset comparison on Group (ii) datasets originally used by five baselines: For more convincing comparison, we evaluate on the same datasets used in the original works of five baselines: 27 classification datasets in GradTree, 4 regression datasets in soft tree [Irsoy et al. 2012], and 5 shared regression datasets among DGT-Linear, TAO-Linear and DTSemNet. Dataset information is given in Appendix H Besides using same datasets, we also compare directly with the results reported in their own papers. For fairesss, our method is evaluated using each baseline's experimental setup, including same data preprocessing and evaluation metrics. Full implementation details are given in Appendix K.2 For GradTree, with detailed results for each dataset given in Appendix K.3 Table [5] our method outperforms GradTree's reported testing results by an average of 4.99%. Regarding soft tree, results in Appendix K.4 Table I6, show that RADDT achieves 6.88% higher test accuracy, again aligning with prior trends. Regarding DGT-Linear, TAO-Liner DTSemNet. the DTSemNett work directly reports TAO-Linear's ' original results due to the absence of open-source code for TAD-Linear. Since DTSemNett itself is tree with linear predictions, for consistency, it adapts the original DGT tree with constant predictions to a linear variant DGT-Linear. Following this comparison from DTSemNet, under same experimental setup. As in Appendix K.5 Table 17 ours outperforms these baselines on out of datasets (except "YcarPred"), achieving the best average rank of 1.6, followed by DTSemNet with 2.4, TAD-Linear with 2.6, and -GT-Linear with 3.2, further supporting our previous findings.
and
extend DTSemNet's Table by including our results
Statistical analysis regarding T While Table empirically shows that RADDT is superior to the other compared trees, we further conduct paired T-tsst to statistically validate the significant dif- ference among these tree methods. The null hypothesis asserts that RADDT is not significantly different from other trees. calculated p-value is less than tolerance т, the null hypothesis can be rejected, indicating statistical significance. The t-statistic (black point), p-value and 95% confidence shown in Figure The results for all comparisons with < T = 0.1 and positive t-statistics consistently indicate that RADDT is superior to these compared decision trees with statistical significance.
20
p-0,000
p 0.000
0-0.005
T-stutistic
p
p-0.019
P-0.001
10
P-0.007
p. 0-0.001
+2.923
+4.208
+4.111
+3,077
+5.164
43.295
44 068
01
CART
OC1
RandČART HHČART GradTroe
SoiDD
ORT-LS
Figure 2: Paired T-test comparing RADDT with other trees (setting significance level 0.1).
Comparison against tree ensembles on Group (i) 17 datasets: Following decision tree com- parison, we proceed to compare our method with RF, XGBoost and TEL to validate its competitive accuracy. Our RADDT slightly underperforms tree ensembles on average. In contrast, RADDT-Linesn outperforms RF by 2.01% XGBoost by 1.12% and TEL by 0.76%, as shown in Table 2 The superior- ity of RADDr- further supported by Friedman rank, where RADDT-Linear ranks highest, matching that of XGBoost. Detailed results for each dataset are provided in Appendix K.] These findings highlight that our method even performs competitively compared tree ensembles. For fair comparison with tree ensembles, this experiment has performed hyperparameter tuning with 300-combination search, including depth up to 50 and number of trees up to 500, following guidelines from [Oshiro et al. 2012 Probst et al. 2019]. Detailed tuning procedures are given in Appendix [] In addition to this 300-combination parameter tuning for ensembles, we also conduct more extensive tuning like 10,000 00.00-combination search in Appendix[K.a Despite extensive tuning, our key findings remain unchanged, and the statistical Friedman rank shows no significant difference. Importantly, our aim is not to claim superiority over ensembles. Since any base learner can be improved via
7

---

ensembling like bagging, comparing a single tree to ensembles is inherently unfair. Instead, we provide a reference showing that our tree can match ensemble's 's accuracy with far fewer parameters.
Table 2: Test accuracy for our trees and 3 tree ensembles on 17 medium-sized datasets in Group (i).
RF
XCBoost
TEL
RADDT
RADDT-Linear
Number of Trees Test Accuracy (RS, %)
314.71
352.94
10
82.62
83.51
83,87
82.39
84.63
Friedman Rank
2.88
2.24
3.29
4.35
2.24
5.2 Superior testing accuracy analysis: from training optimality perspective
To figure out the reason behind the superior testing accuracy, we then analyze the optimality of training. Training trees with different depths correspond to different optimization tasks. To assess optimality, training trees at fixed depth is a common practice. Fixed depths of D = {2, 4, 8, 12] are used for comparison. Table 3 shows that our RADDT outperforms ORT-LS by 5.35%, 2.66% and 0.02% in training accuracy for depths of 2. 4, and 8, respectively, while outperforms CART by 24.83%, 21 ..02% and 9. 9.48% across various depths. For other gradient-based based trees, RADDT significantly outperforms GradTree and SoftDT on average at all depths. LatentTree and DGT do not scale to depth 12. On average across these feasible depths, in training and 6.24% in testing accuracy, and surpasses DGT by 7.52% in training and 2.66% in testing accuracy. Improvements in training accuracy imply that optimization algorithm achieves better training optimality. Furthermore, an increase in training accuracy correlates with the improved test accuracy at depths of 4, and 8, suggesting that an optimized tree with higher training accuracy can potentially yield better test accuracy before encountering serious overfitting issues. Overfitting. particularly depth of 12, is simply addressed by tuning an optimal tree depth. The overfitting limitation is further analyzed in Section 5.6
method outperforms LatentTree by 10.39%
Table 3: Fixed-depth comparison of training, testing accuracy and training time on Group (i) datasets.
Gready Methods
Gradient-based Trees SoftDT
Local Search ORT-1s
Ours
CART
RankCART
HBCART
DC1
GradTree
DGT
LatenTree
RADDT
46.95
32.81
46.20
49.59
39.42
50.59
64.48
71.78
Train
61.16
54.09
62.65
63.21
53.29
56.83
75,83
72.25
79.52
82
(R2 56)
81.45
77.51
82.26
81.43
64.65
66.81
82.01
74.54
90.91
90.93
93.45
93.06
94.74
93.02
66.86
73.03
97.46
96.36
46.14
52.47
45.61
47.95
38.53
49.94
63.81
66.42
64.51
70.07
Test
58.92
52.69
61.30
60.22
51.45
56.32
75.16
71.03
75.06
78.98
(R².5) .))
8
69.77
69.93
74.57
69.08
62.40
66.44
79.99
70.77
74.93
77.89
68.28
64.13
68.37
63.57
63.81
72.45
68.25
73.11
0.03
0.70
4.43
3,216
31.32
22.24
2,102
1,624
457.21
542.22
7.45
4,192
54.74
81.88
2,577
2.194
478.81
(6)
0.07
5.08
12.52
4,803
298.92
1,209
4,049
2,381
9,336
602.69
0.10
12.61
22.01
5,103
10,417
54,829
210.141
2.643
Training optimality comparison against global optimal solutions on Group (iii) datasets: The above results reveal that our approach achieves superior training optimality. To provide a reference for global optimality, we then compare it with global optimal trees ORT-MIP However, ORT-MIP fails to find optimal trees for any of the above datasets, even with 128 cores and a two-day time limit. It can only solve 2-depth tree on 4 small datasets in Group (iii) optimality gap. Despite the existence of sparse optimal trees (Zhang et al. 2003). a direct comparison is infeasible for some reasons discussed in Appendix [K.]] We also detail train accuracy comparison there. Results show that RADDT nearly reaches global optimum (ORT-MIP) with 2.82% discrepancy.
global optimum with 1 1%
Training optimality comparison against ground truth on Group (iii) datasets: We further evaluate RADDT on three synthetic datasets with known ground truth, each with 5000 samples. The procedure for generating synthetic datasets is detailed in Appendix H The corresponding ground truths for
training and testing accuracy are 100%. In Appendix K.8) Table 20 our RADDT closely approximates global optimality in training and testing accuracy, with 0.64% difference over ground truth on average. These results, together with the previous global solution comparisons, further validate the effectiveness of our tree optimization.
Ablation study on the optimization strategies: The notable training accuracy of our RADDT method can be attributed to two key strategies designed to enhance approximation accuracy: the multi-run warm start annealing strategy, which improves training accuracy by an average of 7. 11 across various depths compared to standard softmin function without any scaling; and the strategy of adjusting
8

---

initial solutions for gradient- based optimization, which contributes an additional 1.8% improvement on average. Detailed results for the ablation study are provided in Appendix K.9
5.3 Scalability assessment to 12-depth trees on million-scale datasets in Group (iv)
Previous experiments focus on three different groups of datasets with fewer than 41k samples. To further evaluate our scalability, we test on seven large-scale datasets, each containing at least I million samples, using the same fixed-depth setting as in Table 3 The Group (iv) dataset is detailed in Appendix H As shown in Appendix K.10 Table 22 our RADDT successfully scales to a 12-depth tree, outperforming CART by 4.83% in training and 3.15% in testing across all depths. In contrast, GradTree and SoftDT fail to output good solutions. At the feasible depths for DGT and LatentTree, RADDT outperforms DGT by 3.9% in training and 3.74% in testing on average, while it slightly underperforms LatentTree by 0.03% in training and 0.08% in testing. However, RADDT takes significantly less training time, and LatentTree is only solvable at depths 2 and 4. These comparisons effectively showcase RADDT's scalability on million-scale datasets at depth-12 12 trees.
GPU acceleration and training time analysis: Our training time is primarily affected by sample size nt feature number p and depth D. For D-depth tree training, each sample must be evaluated at all 2D - 1 branch nodes via matrix operation Ax,, requiring Opp (2 - -]) operations per sample and On p- (2 - 1)) operations for the full dataset. It indicates that training time increases with larger and D. Importantly, our implementation is highly parallclizable and facilitates multi-GPU acceleration. The specific GPU configurations in our experiments and acceleration analysis are given in Appendix K. In the million-scale comparison Appendix K.10 Table 22 our RADDT achieves 42-fold speedup over DGT at depth 4. These scalability advantages become even more pronounced with deeper trees and more samples, where larger matrix operations dominate the computation. However, in this setting within Table [22] most high-accuracy baselines fail to scale to depth 12, making direct comparisons at that depth infeasible. To further illustrate the advantage, we refer to 3 where the second-best method ORT-LS scales to depth 12. For instance, on the "ailerons" dataset, RADDT is 432 times faster than ORT-LS, demonstrating the substantial speedup deeper depths. Detailed time comparisons for datasets with more than 10,000 samples used in Table are given in Appendix K.12 Besides, a training time comparison of our method in GPU versus CPU settings is provided in Appendix K.13 although the ad vantages of GPU accelcration are expected.
5.4 Analysis of model complexity and inference time
Alongside tree depth, the number of model parameters also offers a clear view of model complexity. While oblique tree typically requires more parameters than orthogonal tree at given depth due to feature combinations, often yields better accuracy with much smaller depth. Therefore, for a similar accuracy, oblique tree may not require more parameters overall than orthogonal tree.
For D-depth binary tree with T3 2D_ branch nodes and Tr = 2n Icaf nodes, and a dataset with features, orthogonal tree like CART requires 2 - TB + Tr parameters. In contrast, our oblique tree RADDT requires TB 1++++++777 1+T parameters, while our
needs TB-P+I4 1 Tp+
parameters. Based on these, we compare the number of model parameters for CART, RADDT and RADDT-Linear in Table 4 by averaging across all Group (i) 17 datasets. As shown in Table 4 CART achieves 74.85% accuracy with average depth 10.24 and 3,140.94 parameters. Our RADDT and RADDT-Linear reach 82.39% and 84.63% accuracy at depths 7.29 and 4.82, using 10,503.94 and 4,044.71 parameters, respectively. Notably, if the goal is to match or slightly exceed CART's accuracy, our models can do so with much smaller trees. Table shows that RADDT achieves 75.23% at depth 2.82 using only 101.71 parameters, and RADDT-Linear reaches 77.21 at depth with just 40.47 parameters, yielding 31 times and 78 times reductions in parameter count compared to CART. These results indicate that our methods do not necessarily require more parameters for improved accuracy; the total parameter cost depends on the desired trade-off between accuracy and model complexity.
Additionally, inference time greatly helps assess model complexity. In the setting of Table I and Table our methods achieves superior accuracy improvements but involves more parameters than CART, resulting in slightly higher inference time. However, if only aiming to achieve an accuracy comparable to CART (74885%). Table 4 shows that the inference time of RADDT becomes comparable to CART, while RADDT-Linear is even faster. It is important to note that our implements use Python

---

Table 4: Model complexity and inference time comparison with CART on Group (i) 17 datasets.
Method
Testing Accuracy (I²",
Depth
Number of Branch Nodes
Leaf Nodes
Number of
Model Parameters
Total Number of Inference Time
(Millisccond)
CART
74.85 (reported in Table
10:24
1,046665
1,047.65
3,140.94
0.44
82,39 (roported in Table 3)
7.29
671.94
672.94
10,303.94
L88
BADDT
75.23 (only slightly exceed CART's accuracy)
2.82
6.88
101.71
0.54
RADDT-Linear
84.63 (reported in Table 3)
4,82
129
130
4,044.71
166
77.21 (only slightly exceed CART's accurncy)
40.47
and PyTorch, where inference time may not scale strictly with parameter count due to framework overhead. A pure C++ implementation would likely align more closely with parameter count.
5.5 Interpretability analysis
We fully acknowledge that orthogonal trees like CART, at the same depth, are generally more inter- pretable than oblique trees. However, as originally analyzed in OC1 MMurthy et al.) [994]. oblique trees could become more interpretable when their depth is substantially smaller. Interpretability depends on multiple factors including tree depth, feature number, and the accuracy-simplicis trade-off. There is no interpretability superiority of one approach over the other, as it depends specific application scenarios. We evaluate our RADDT's interpretability from three aspects: tree-based prediction logic, unique prediction path and the complexity of decision rules. Detailed analysis be found in Appendix K. 14 with an illustrative example in Figure
5.6 Limitations analysis and future work
While our approach achieves superior accuracy, several limitations remain. The primary limitation lies in inadequate regularization. In Table while training accuracy for RADDT improves by 5.43%
from depth 8 to 12, testing accuracy conversely drops by 4.78%, indicating a serious overfitting issue. This issue is more pronounced in trees with linear predictions, as detailed in Appendix K.15 In response, we apply preliminary L1 regularization RADDT-Linear for experiments in Table 2 leading to a modest 0.57% improvement in testing accuracy. Due to the challenges in identifying optimal regularization strength and potential increases in training time, we just used a small value of le- -4 4. without extensive tuning. Despite this, further improvements could be achieved through more dedicated regularization strategies, such as the post-hoc regularization technique. Hicrarchical Shrinkage. proposed for trees by Agarwal et al. [2022]. Second, the effectiveness of our multi-run warm start annealing strategy is validated by empirical observations; however, a theoretical analysis is still lacking. Third, our tailored initialization adjustment strategy fails to consider the corner case of an ill-defined initialization where both a, 0 and by- 0. This is also limitation, despite its rarity and minimal impact on empirical performance in practice. Fourth, while our current hyperparameter tuning for tree ensembles is sufficient support our main claims, especially given that our goal not to claim superiority over ensembles, more tuning on regularization parameters could potentially yield even better results for tree ensembles. Exploring this gap between a single tree and ensembles presents promising area for future research. Next interesting future direction is to apply our optimization strategies, such as initialization and multi-run warm-start annealing, to other gradient-based trees like SoftDT. Since these strategies are general, they are not limited to our specific tree formulation and may benefit other models. Another promising alternative to our scaled softmin approximation is the Entmax function. However, its application requires further investigation, as selecting its sparsity parameter presents a similar challenge to choosing the scale factor in our softmin method.
Conclusion
Our approach addresses two main limitations of classic decision tree: non-differentiabiliy and low test accuracy, thereby enhancing its practicality. We tackle these issues by first proposing a "ReLUUArgmin" b-bsed hard split tree with a novel exact reformulation, then significantly improving its test accuracy through our gradient-basse based entire tree optimization. The entire tree training problem is reformulated as an unconstrained optimization task, with scaled softmin function approximating Argmin behaviors for effective gradient backpropagation. Our reformulated tree, unlike existing soft approximation, eliminates the softness at both branch nodes and leaf nodes, thus preserving hard splits and deterministic predictions. Extensive experiments demonstrate our tree's 's superior accuracy and scalability million-scale datasets.
10

---

Acknowledgments and Disclosure of Funding
Yankai Cao acknowledges funding from discovery program of the Natural Science and Engineering Research Council of Canada (RGPIN-2019-05499) and New Frontiers in Research Fund (NFRFE- 2022-00663). The authors also gratefully acknowledge the computing resources and services provided by Digital Research Alliance of Canada (www.alliancecan.cu and Advanced Research Computing the University of British Columbia.
References
Daniël Vos and Sicco Verwer. Optimizing interpretable decision tree policies for reinforcement learning, 2024.
11632
Sascha Marton, Tim Grams, Florian Vogt, Stefan Lüdtke, Christian Bartelt, and Heiner Stucken- schmidt. Mitigating information loss in tree- based reinforcement learning via direct optimization, 2025. URL http://arxiv org haarrg/baa244000 08761
Vinícius G. Costa and Carlos E. Pedreira. Recent advances in decision trees: An updated survey. Artificial Intelligence Review, 56(5):4765-488) 2023. doi: 10. 1..1007/10446--022- 10275-5.
Haoran Zhu, Pavankumar Murali, Dzung Phan, Lam Nguyen, and Jayant Kalagnanam. A scalable mip- based method for learning optimal multivariate decision trees. In Advances Neural Information Processing Systems, volume 33, pages 1771-1781. Curran Associates, Inc., 2020.
Leo Breiman, Jerome Friedman, Charles J. Stone, and Olshen. Classification and Regression Trees. Taylor& & Francis, 1984. ISBN 978-0-412-04841-5
S. K. Murthy, S. Kasif, and S. Salzberg. A system for induction of oblique decision trees. Journal of Artificial Intelligence Research, 2:1 2:1-32, 1994. doi: 10.1613/jair.63.
D. C. Wickramarachchi, B. L. Robertson, M. Reale, C. J. Price, and J. Brown. Hheart: An oblique decision tree, 2015.
Rico Blaser and Piotr Fryzlewicz. Random rotation ensembles. Journal of Machine Learning Research, 17(4):1-26, 2016.
Arman Zharmagambetov and Miguel Carreira-Perpinat Smaller, more accurate regression forests using tree alternating optimization. In Proceedings of the 37th International Conference on Machine Learning, pages 11398-11408 PMLR, 2020.
Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning, 106(7):1039- 1082, 2017. doi: 10. 10.10077/119944-0--55633
Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo Seltzer. Generalized and scalable optimal sparse decision trees, 2022. URL http://arxiv. wttg///////aaaeeooo httt:://arrav.oorg/b////26..... 08690
Justin Boutilier, Carla Michini, and Zachary Zhou. Optimal multivariate decision trees. Constraints, 2023. doi:
Jack William Dunn. Optimal Trees for Prediction and Prescription. Thesis, Massachusetts Institute of Technology, 2018.
Ajaykrishna Karthikeyan. Naman Jain, Nagarajan Natarajan, and Prateek Jain. Learning accurate decision trees with bandit feedback via quantized gradient descent, 2022.
Sascha Marton, Stefan Lüdtke, Christian Bartelt, and Heiner Stuckenschmidt. Learning decision trees with gradient descent, 2023.
Subrat Prasad Panda, Blaise Genest, Arvind Easwaran, and Ponnuthurai Nagaratnam Suganthan. Vanilla gradient descent for oblique decision trees, 2024.
Ozan Irsoy, Olcay Taner Yıldız, and Ethem Alpaydın. Soft decision trees. Proceedings of the s International Conference Pattern Recognition (ICPR2012), pages 1822, 2012.

---

Alvin Wan, Lisa Dunlap, Daniel Ho, Jihan Yin, Scott Lee, Henry Jin, Suzanne Petryk, Sarah Adel Bargal, and Joseph E. Gonzalez. Nbdt: Neural- decision trees, 2021.
Nicholas Frosst and Geoffrey Hinton. Distilling a neural network into a soft decision tree, 2017.
Hussein Hazimeh, Natalia Ponomareva, Petros Mol, Zhenyu Tan, and Rahul Mazumder. The tree ensemble layer: Differeentiability meets conditional computation. In Proceedings of the 37th International Conference on Machine Learning, pages 4138 4148. PMLR, 2020.
Yongxin Yang, Irene Garcia Morillo, and Timothy M. Hospedales. Deep neural decision trees, 2018.
Mohammad Norouzi, Maxwell Collins, Matthew Johnson, David Fleet, and Pushmeet Kohli. Efficient non- non-greee greedy optimization of decision trees. In Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015. URL http://tttp:/ppooeeeieiii new..inu.ppppp. ec/ .tmal
Guang-He He Lee and Tommi S. Jaakkola. Oblique decision trees from derivatives of relu networks, 2020.
http://orrrgbbb//g.////// 13488
Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson. Rodrigo Santa Cruz, and Edison Guo. On differentiating parameterized argmin and argmax problems with application to bi-level optimization, 2016.
Valentina Zantedeschi, Matt Kusner, and Vlad Niculae. Leamingg binary decision trees by argmin differentiation.. In Proceedings of the 38th International Conference on Machine Learning, pages 12298-12309. PMIR, 2021.
Qianggiang Mao and Yankai Cao. Can single tree outperform an entire forest?, 2024. URL http://arxiv.or org/ /a//abbb////..// 2411.17003
J. R. Quinlan. Learning with continuous classes. In Proceedings Australian Joint Conference on Artificial Intelligence. pages 343 3488 Singapore, 1998. World Scientific. URL http://wwww With
researchgate htt.://.......eeeee.aaaa.aaaaaaa
David Bertoin, Jérôme Bolte, Sébastien Gerchinovitz, and Edouard Pauwels. Numerical influence of relu'(0) (0) on backpropagation. In Advances Neural Information Processing Systems, volume 34, pages 468-479. Curran Associates, Inc., 2021.
Gian Paolo Leonardi and Matteo Spallanzani. Analytical aspects of non-differentiable neural networks, 2020.
Thomas Hehn and Fred A. Hamprecht. End-to-end learning of deterministic decision trees, 2017.
David J. Sheskin. Handbook of Parametric and Nonparametric Statistical Procedures, Fifth Edition. CRC Press, 2020. ISBN 378-1-4398-58044
Thais Mayumi Oshiro, Pedro Santoro Perez, and José Augusto Baranauskas. How many trees in random forest? In Machine Learning and Data Mining in Pattern Recognition, pages 154-168, Berlin, Heidelberg, 2012. Springer. ISBN 978-3-642-31537-4 doi: 10. 10.10077978--366--31557-4 13.
Philipp Probst, Marvin N. Wright, and Anne-Laure Boulesteix. Hyperparamettess and tuning strategies for random forest. WIREs Data Mining and Knowledge Discovery, (3))= 2019. doi: 10. 1002/ widm. 1301. /ttps:t////
www.ly.c.mmd.i/....oo wwwpoo//aw///////ooooooooooaa//t http://bbb.1.0.00//v...... 1002/widm....mmmmm 1301
Rui Zhang, Rui Xin, Margo Seltzer, and Cynthia Rudin. Optimal sparse regression trees. Proceedings of the AAAI Conference on Artificial Intelligence, 37(): I 1270-1 2023. doi: 10. 1609/aai.. v3719. 26334. URL/https: / ojj.. aaai. orooooog/iooo http/indxx....
Abhineet Agarwal, Yan Shuo Tan, Omer Ronen, Chandan Singh, and Bin Yu. Hierarchical shrinkage: Improving the accuracy and interpretability of tree-based models. In Proceedings of the 39th International Conference on Machine Learning, pages 111-135, PMLR, 2022. URL https //proceedings mlr. prwss/v162. v162/ hgppwaallbwabba...
Dheeru Dua and C. Graff. UCI machine learning repository., 2019. 2019.
12

---

Joaquin Vanschoren, Jan N. van Rijn, Bernd Bischl, and Luis Torgo Openml: Networked science in machine learning. SIGKDD Explor Newsl., 15(2):49 60, 2014. doi: 10.1445/2441100226111999
URL atttps://dl acm. 1145//0////1111114411111 2641198
13

---

Appendices for: Differentiable Decision Tree via "ReLUUAArgmin" Reformulation
A
Certain Scenarios Requiring Decision Trees with Hard-splits
Hard-split decision trees and soft decision trees represent fundamentally different models, each suited different application scenarios. Further, there do exist scenarios where the application of hard-split decision trees is not only more appropriate but also imperative. Below is an illustrative example from industrial projects that underscores this preference.
Scenario: Piece-wise affine control law in explicit model predictive control.
In explicit model predictive control, the control law is often represented by piece-wise affine functions, which can be effectively approximated by a hard-split decision tree. The hard decisions at branch nodes can be used to determine the control action based on the state of the system, which can be easily implemented in real-time control systems.
Beyond the utility of making clear hard decisions, the optimal decision tree model that offers superior predictive performance also crucial for these scenarios. From the perspective of application scenar- ios, the motivation and necessity for hard-split optimal decision trees are intuitive and compelling.
B Empirical Analysis of Scale Factor Impacts on Scaled Softmin Operation
The scale factor significantly influences the approximation degree Argmin function and the behavior of its gradient in optimization. A larger a leads to a better approximation than standard softmin function with a I, achieving closer proximity to Argmin function as a approaches infinity. An illustration for the gap between scaled softmin function and the Argmin function under varying shown in Figure Nonetheless, a larger a also results in a more unstable gradient, which may adversely affect the optimization process. Consequently, the represents critical balance between achieving high approximation degree and maintaining stability optimization processes.
To show how the scale factor impacts the training optimality of the unconstrained optimization problem (our RADDT method without using the strategy of multi-run warm start annealing), we conduct comparison experiments across different a values at different depths. Our differentiable decision tree optimization framework will be introduced in Section The findings, summarized in Table 5 reveal the relationship between a and training performance, as measured by the average training accuracy R²2 Notably, we observe that the training accuracy at the extremes of softmin function) and a = 1000 are inferior compared to intermediate a values. This observation underscores two critical insights: first, relying solely on softmin function (a = 1) yields suboptimal optimization results; second, the high value may not necessarily lead to better optimality.
(standard
Table 5: The impact of a on training accuracy across different depths.
Training Accuracy (S)
Various
17
1)
13
(Standard Softmin Function) a 20
60.78
69.97
81.46
93.45
70.28
79.43
87.98
94.49
150
68.00
78.31
88.08
1000
65.05
74.16
83.79
93.45
However, it remains a challenge to identify the optimal scale factor that balances the trade-off between approximation degree and differentiability. To mitigate this issue, we propose a multi-run warm start annealing strategy, detailed in the following Section 4.1 to narrow the gap between the Argmin behaviors and its differentiable approximation.
C Deterministic Calculations for Leaf Prediction Parameters
As detailed in Section 3.2 our method deterninistically calculates the leaf prediction parameters 0 (i.e., the parameters and regression, and the parameters h classification), instead of directly using trained values for 0. Given tree with tree split parameters A and b, the deterministic tree path
14

---

for each sample can be obtained, which allows determining the total number of samples assigned to a specific leaf node E T.,
In classification tasks, the value of h at a leaf node i corresponds to the majority class among the samples assigned to that leaf node. In this case, the leaf value is represented as a class label or the one-hot vector specific to the class, he E {0, 13 in contrast to the continuous value h, E R used during the training phase.
In regression tasks, we consider two types of leaf prediction: linear prediction and constant prediction. For decision trees with linear predictions, the prediction at leaf node is linear combination of input features by fitting a linear correlation between all samples assigned to that leaf node. The leaf values at leaf node t, k, and hy, are the linear coefficients determined by linear regression. For decision trees with constant predictions, the value of K remains zero. The value of h at a leaf node I. is an average of the true output values (y:) of the samples assigned to that leaf node t.
D Implementation Details of Multi-run Warm Start Annealing
As discussed in Section 4.1 the key challenge in enhancing the approximation accuracy to Argmin behaviors lies in the selection of a. A larger a may destabilize optimization process, whereas a smaller tends to be easier to solve for gradient- based optimization. The annealing strategy, which gradually changes a from small to large values, has been ever used to strike such a balance in existing literature [Hehn and Hamprecht] 2017 Karthikeyan et al.) 2022 Lee and Jaakkola 2020), though not specifically for our application to scaled softmin. However, their annealing typically adjusts a within single training process, such changing a every few epochs, which may affect stable gradient updates. Besides, the implementation details in these works are not well-documented. Considering these, we introduce a detailed description of our annealing strategy.
Our annealing process operates across multiple optimization runs with different a values. The solution from an optimization task with smaller is used to effectively warm-start the next optimization run with a larger a. By starting with a smaller scale factor and gradually increasing it, this strategy enhances the approximation accuracy, while mitigating numerical instability typically associated with larger scale factors.
Specifically, the procedure begins by sampling set of scale factors within a predetermined range from the smallest Omai to the largest Omars ensuring a broad exploration of possible a values. We adopt log-space sampling to generate these scale factors, {ai,... ), evenly on logarithmic scale. In this case, these sampled scale factors can be denser in the smaller range, which is beneficial for the stable optimization process. We initiate the optimization with the smallest sampled scale factor to generate the initial optimized tree candidate. This candidate then serves as the starting point for the next optimization run with slightly larger a. This iterative process is repeated until all sampled scale factors have been utilized. Detailed implementation steps are integrated within our systematic optimization framework, Algorithm
D.1 Comparison between our annealing strategy and binary search for scale factor selections
Binary search provides a structured way to explore different a values for scaling the softmin approxi- mation. Unlike random trials, it narrows the search range by evaluating performance at the midpoint and adjusting boundaries accordingly. While this is more principled than random guessing, it still involves testing isolated values. As earlier discussed, this approach does not match the performance of our multi-run warm start annealing strategy.
While we agree that a binary search-like approach can be used to identify an effective a, our empirical results show that gradually increasing a, rather than directly using a large fixed value, leads to better training outcomes. This is because starting with smaller a allows the model to optimize under smoother case, improving stability. As a increases, it becomes sharper and closer to the ideal formulation, and the model benefits from being progressively adapted to this more accurate approximation. Our annealing strategy takes advantage of this effect by warm-starting each successive optimization task with the solution from previous task with smaller a. This gradual refinement enhances the approximation accuracy, while mitigating numerical instability typically associated with larger
15

---

The average training accuracy across Group (i) 17 regression datasets for different tree depths is summarized below. Our annealing strategy consistently outperforms binary search, with an average improvement of 2.82% across all depths.
Table Training accuracy (optimization capability) comparison with different a selection strategies.
Tree Depth
2
4
8
12
Using Binary Search for Selections
69.95
77.33
87.69
94.98
Using Our Multi-run Warm Start Annealing Strategy for Selections
71.78
82.18
90.93
96.36
These results validate the effectiveness of our annealing in practice. However, acknowledge that this finding is based on empirical observation, and a theoretical analysis is still lacking.
E
An Illustrative Example of The Influence of Initial Solutions and Their Adjustments for Gradient-based Optimization
As discussed in Section especially in our task with softmin operations. This because our softmin operates on U2., which is ReL.Ubbased violations with either zero or non-zer con-zero values. However, these non-zero violations may be close to zero, especially for samples around the decision boundary a æ; b, = While such small discrepancies between exact-zero and near-zero violation do not impact Argmin behaviors, which select the unique path only when U 0, they can sensitively affect softmin. Specifically, softmin may fail to produce values close to one as ideally expected, potentially compromising approximation accuracy. Here, we provide an illustrative example to understand the influence of initial solutions and their adjustments for gradient-based optimization. As shown in Figure 3 the red sample x" lies near the blue decision boundary, resulting a small positive ReLU output, close to zero, that is difficult to distinguish from an exact zero.
good initial solution is crucial for achieving a better optimality,
Decision Boundary line with initial a, and by near sample af x, -
Samples assigned to right
Samples assigned to left
ULi of U-,, close to acro Adjusted a, and by with more margin to nearest samples
UL 0
Figure Illustration of the influence of initial solutions and the effective adjustments.
To mitigate this, the initial A and b can be adjusted so that the decision boundary achieves the maximum margin from the nearest samples, without altering the existing sample assignments as illustrated by the green line in Appendix B Figure 3 This adjustment does not change sample assignments but enhances the distinction between exact-zero and near-zero cases.
The adjustment can be easily implemented either by calculating the median of a. x; for the closest samples on both sides of the boundary, or using support vector machine treat sample assignments as a binary classification task. To be more specific, Each branch test a. x; < by acts as binary classifier, directing samples left or right. boundary (e.g., by modifying the median of a, x;)) to enlarge the margin without changing sample assignments. Beyond only adjusting by. we also refine both a, and by using an SVM: we treat left/right assignments weights and bias update the split parameters while preserving the original assignment. This procedure is visualized in Appendix Figure
practical adjustment is to slightly shift the decision
binary labels and fit linear SVM to maximize margin. The resulting
16

---

Hyperparameters Analysis of Our Differentiable Decision Tree Optimization Approach
Despite the introduction of additional hyperparameters gradient-based optimization, tuning them is not typically necessary because their effects are straightforward. To be more specific, the hyperpa- rameters our differentiable decision tree optimization approach are as follows:
(1) The multi-start number Natort
95
Natart
Natart 1
Training Accurscy (%9
80
70
2
8
10 12
Depth
Figure 4: The trend of training optimality under different depth setting with different Nstarts
The multi-start number Nstart directly influences training optimality by increasing the chance of finding the optimal solution, albeit higher computational cost. In practice, Nstort set to balance acceptable computational expenses with desired training accuracy.
To explore the correlation between Nstart and the training optimality, our "ReLU+ bbase Differentiable Decision Tree Optimization (RADDT) for regression trees with constant predictions is performed under different N Netert values shown in Figure 4 It indicates that increasing Netart generally improves training optimality for all various tree depths, especially at lower tree depths.
(2) The epoch number N Napoch
The epoch number Nepoch is another hyperparameter that directly affects training optimality. A higher Nepoch value increases training accuracy, but it also increases computational costs. In practice, Nepoch also to balance acceptaale computational expenses with desired training accuracy.
Our experiment with different Nepoch = (100, 3000, 5000) in Figure shows that increasing Nepoch generally improves training optimality for all various tree depths.
Napoct 1000
Napoch 3000
Napoch 5000
Training Accuncyy (%)
90
85
80
75
Tree Depth
Figure 5: The trend of training optimality under different depth setting with various N Nepoch.
(3) The range of sampled scale factors [ammin amaz] for scaled softmin function
17

---

1.0
a
SUS
s(U).))
em-
= 10
Sealed Softmin Function Value
0.8
161
50
a 100
a 200
Argmin
0.0
0.3
0.5
0.9
U,
Figure 6: Comparison of scaled softmin function approximating Argmin behaviors under varying
This predetermined range is used to sample a set of scaled factors a for the strategy of multi-run warm start annealing. The principal aim is explore broader range scale factors, ranging from smaller to larger values. As discussed in Section 3.2 the scaled softmin function applied to UL. is used to approximate the Argmin function (more concretely, the one-hot encoded Argmin function). A larger leads to closer approximation to the Argmin function. As observed in Figure the gap between scaled softmin function and the Argmin function narrows as a increases. Noticeably, the standard softmin function with I exhibits significant deviation from the Argmin function as depicted in black line. With a larger a, such as 2 50, the scaled softmin function closely approximates the Argmin function, almost overlapping with the Argmin function as shown in the figure. In the implementation our experiments, we simply sample a within the range [Omsn Om = [2. 200) to meet requirements. This range ensures that smaller values maintain smooth gradient and exhibit a better approximation than the standard softmin function, while larger values closely approximate the Argmin function.
(4) The number of sampled scale factors
Within a predetermined range, set of scaled factors, denoted as {a1, Jn J. are sampled for subsequent in multi-run warm start annealing, detailed in Section 4.1 Larger scale factors reduce the approximation disparity, whereas smaller ones yield smoother and more stable gradient. Including a greater number of scale factors in the set facilitates a more stable approximation process, enhancing the approximation degree to Argmin behaviors while minimizing the loss of differentiability typically associated with larger scale factors. Intuitively, including more scale factors the enhances training optimality. However, this leads to increased iterations in the annealing strategy, thereby raising computational costs. Practically, the number scale factors often determined by balancing training accuracy against computational demands. In our experiments, to avoid excessive computational costs, we primarily sample scale factors with a log- space distribution within the range [Okminn [mann.
(5) The learning rate
The learning rate is a common parameter in gradient- baade optimization, and has garnered significant attention in the literature. To simplify its usage, adopt the well-cstablished learning rate scheduler, termed CosineAnneall ing.enneestarrree.ommmmmmoo.eeee (with initial linear warm up) in Py PyTorch, which decreases the learning rate from initial value of 0.01, thus minimizing the need for additional tuning.
G Algorithm Details of "ReLU+Argmin "-based Differentiable Decision Tree
Alongside the detailed descriptions in Section 4.3 we present the algorithmic implementation of our URel.U+Argminn basse Differentiable Decision Tree Optimization framework, RADDT, in Algorithm
18

---

Algorithm The entire tree optimization framework for RADDT.
1:
Input: (æi, 34 Ti tree depth D. learning rate 1). epoch number Nepoch. multi-start number N Natort.
Output: Optimal trainable variables Abests Dbeat, Bbeat.
3: Define Lmin, empty variables Abest, bbest and Oeest-
4: for start = 1 to Nstart do
5: Initialize A, b, 8 with initial solution adjustments detailed in Section foi,-.. ,On,] with log-spacing. for osste E {an..... (n.) do
4.2
Generate scale factors
7: If iler * 1. initialize trainable variables with the solution of last optimization run by Line 12
8: for k = to Nepoch do
9:
Calculate loss C at step by Equation 7 and calculate variables via gradient decent, such A++1 A end for
ac
ac
Then update trainable
55
26
10:
11:
Deterministically update & without any approximation, as described in Appendix C
12:
Generate tree candidate with optimized variables, termed as Atter biter. Uiter- Specifically. Aster ANepoch and Diter bNepack. while Oster is derived through deterministic recalculation as mentioned in Line
13:
Deterministically compute & by Equation 5 IF L < bmins update variables like Abest + Aster-
14:
end for
15:
end for
H Detailed Description and Usage of The Four Groups of Datasets
Dataset split ratio and usage
In our experiments, typically, we allocate 75% of the samples for training purposes and the remaining 25% for testing, following the train-test split ratio as used in [Bertsimas and Dunn 2017]. If an experiment requires cross validation for hyperparameter tuning like tree depth, we then subdivide the training datasets into training and validation subsets in 2:1 ratio. The dataset setting accordingly changes to 50% samples as training set, 25% samples as validation set, and 25% samples as testing set. After determining the best hyperparameters, we then retrain the model using the combined training and validation set, and use the remaining 25% as the testing set to evaluate the final testing accuracy.
Dataset information across four groups
As discussed in Section ||| our baseline comparison experiments are conducted across four groups of datasets: (i) 17 medium-size sized regression datasets with fewer than 41k samples (primary focus); (ii) 27 same classification and regression datasets used certain baselines (for more credible comparison their used datasets); (iii) 4 real-world datasets with about 100 samples, and 3 synthetic datasets with 5000 samples (for comparing global optimality with global tree ORT-MIP (Bertsimas) and Dunn 2017] and known ground truth, respectively): (iv) 7 large-scale datasets with at least I million samples (for scalability).
Unless otherwise specified, these real- world datasets used for our regression experiments are collected from the UCI repository (Dua and Graff 2019] and OpenML /Vanschoren et al. 2014). Regarding the 17 medium sized datasets in Group (i), detailed information about these datasets is summarized in Table 7 The dataset size n and the number of features p are provided in the table.
Regarding the same classification datasets used in the original GradTree study [Karthikeyan et al. 2022) in Group (ii), we include these shared datasets support more credible and convincing comparison. Although we have already compared against GradTree on the Group (i) 17 regression datasets in Table 7 and their subpar performance aligns with the results reported in their own Table 1 and 2, where their method underperforms the foundational baseline CART on 17 out of 36 classification datasets, we still further evaluate on the same classification datasets used in their own work to provide more credible comparison. Among their 36 classification datasets, we finally collect 27 and discard 9 datasets, due to one or more of the following issues: unavailable dataset sources, unusable datasets with substantial missing values (corrupted dataset), or ambiguous dataset documentation. For example, the "rice" dataset lacks a clear download source. The "annealing" dataset contains significantly large number of missing values and is nearly unusable. The "splice" dataset lacks clear information, such as the definition of features and predictive target, making this type of dataset unusable. Therefore, to ensure experimental reproducibility and data integrity,
19

---

Table 7: Group (i) 17 real-world regression datasets from UCI and OpenML Repository.
Dataset Index
Dataset Name
Dataset Size (n)
Feature Number (p)
airfoil-sell -else
1,503
space-ga
3,107
3
abulone
4,177
4
pus-turbin--co-miiiiio----
7,384
9
7,384
6
puma8NH
8,192
8
7
cpu-act
8,192
21
8
epu-small
8,192
12
9
kin88m
8,192
8
10
deltu-clevators
9,517
6
combined cycle- power-plant
9,568
12
beeeuical-grid-taablll
10,000
12
13
condition-bused maneeeenminnnneeee..... comppessso
11,934
16
condition maintenance turbine
15
ailerons
13.750
40
16
elevators
16,599
18
17
friedman-artificill
40.768
10
discard datasets in total and perform the same-dataset comparison on the remaining 27 datasets. Additionally, since their work adopts 20% test split, different from our default setting, we adopt their train-test split ratio for this specific comparison ensure fairness. The final list of datasets, along with their sample size n, number of features p, and number of classes c, is presented in Table g
Table 8: Group (ii) 27 same classification datasets used in the original GradTree study.
Datasct Index
Datasct Name
Datasct Size (n)
Feature Number (p)
Class Number (c)
GradTree-1
balance-scule
625
GradTree-2
1,372
GradTree-3
blood-transfusior
748
4
car-evaluation
1,728
4
G
congressional-voiiee
232
16
2
GradTree-6
contraccptive-
1,473
GradTree-7
dermatology
358
G
echncardiogram
61
11
GradTreee-9
iris
150
GradTree- 10
spamhase
4,601
GradTree-11
dtyroidddiisesse-amm-
7,200
GrudTree-11 12
wine
178
GrudTree--3
adult
32.561
14
2
GrudTree-11
bank-marketing
45,211
14
2
GradTree-11
credit-card
30,000
GradTree--6
german
1,000
20
GradTree-17
glass
214
GradTree-18
hcart-failure
299
12
2
GradTree-19
landsat loan-house
6,435
GradTree-20
614
GrudTree-21
lymphography
148
GradTree-22
mushrooms
8,42
22
GradTree-23
raisins
900
GradTree-24
segmentt
2,310
GrudTree-25
solur-flat flare
1,389
GradTree-26
wisconsin breast-cancer
569
GradTreo-27
zoo
101
16
Regarding the same regression datasets used in the work of soft decision trees, no tabular datasets were used in [Frosst and Hinton| 2017). but we adopt the four tabular regression datasets from the original soft decision tree study by [Isoy et al. 2012). We include these shared datasets to support more credible and convincing comparison well. The shared 4 datasets given in Table ?
Regarding the same regression datasets used in DTSemNet, DGT-Linear and TAO-Linear, we also include these 5 shared datasets. We follow the same comparison setting and experimental setup as DTSemNet to include these shared datasets for a more credible comparison against DTSemNet, DGT-Linear and TAO-Linear. Details of the shared datasets are provided in Table 10
For comparison of training optimality in Section 5.2 four small regression datasets with around 100 samples also used. These datasets, collected from UCI and listed in Table II allow us compare
20

---

the training optimality of our method against global optimal solutions. The global optimal method ORT-MIP is computationally solvable for such a small dataset size as observed in our experiments.
Besides, three two-dimensional synthetic regression datasets with 5000 samples each are also used to showcase the effectiveness of our tree optimization in approaching global training optimality. Synthetic datasets are advantagcous as they hold a known ground truth. Based on tree-based decision rules with the form of IF-THEN statements, we design 2 decision rules create a dataset by the D-depth tree. These decision rules are used to assign samples to the corresponding leaf nodes along a sequence of branching tests. For instance, when generating a two-dimensional dataset for 2-depth tree, one of the decision rules is described as IF 24,1 + 24,2 > O and 21,1 2422 > 0, THEN Yi 0.5. In this setting, we generate synthetic datasets, termed "Syn-2", "Syn-3" and "Syn-4". These datasets are created with varying tree depth settings of 2, 3, and 4, respectively.
Table 9: Group (ii) 4 regression datasets used in original work of soft trees Irso et al. 2012
Dataset Index
Dataset Name
Dataset Size (n)
Feature Number (p)
T
abalone
4,177
SoftTree-2
puma8NHI
8,192
SoftTree-3
computer
209
7
SoftTree-4
concrete
103
7
Table 10: Group (ii) five shared regression datasets used in original work of DTSemNet, DGT and TAO.
Dataset Index
Dataser Name
Dataset Size (n)
Feature Number (p)
DeSt
Abulone
4,177
8
DTSemNet-2
Comp-Active
8,192
21
DTSemNet-3
Ailerons
14,308
D4
CTSlice
53,500
384
DTSemNNe-5
YearPred
515,345
90
Table 11: Group (iii) four small real-world regression datasets with about 100 samples.
Dataset Index
Dataset Name
Dataset Size (n)
Feature Number (p)
Small-1
concrete- wareeesssup--------eeee cosp-compeesiive concrete-slump-testteeee hybrid-price 1pga-2008
103
Small-2
103
Small-3
153
4
Small--
157
6
Regarding the 7 large-scale regression datasets each with at least 1,000,000 samples in Group (iv).
they are used to evaluate the scalability of our method. These datasets are listed in Table 12 The dataset size n and the number of features p are provided in the table.
Table 12: Group (iv) seven large-scale regression datasets each with at least million samples.
Dataset Index
Dataset Name
Dataset Size (n)
Feature Number (p)
Million-1
BNG-Ailerons
1,000,000
40
Million-2
BNG-cpu-act
1,000,000
Million-3
BNG-cpu-small
1,000,000
12
Million-4
BNG- HHGG-puma3HH
1,000,000
32
Million-5
1,000,000
32
Million-6
ACSPublicCoverage200
1.138,289
19
Million-7
BNG-elevator
1,000,000
18
I The implementation Settings for Comparison Studies
To implement our "ReLU+Argmin" basse Differentiable Decision Tree optimization framework (RADDT), utilize PyTorch that embeds auto differentiation tools and gradient- optimizers. Our method is configured with N Nopock = 3, 000 and Natart = 10, unless otherwise specified.
For benchmarking, the Scikit-lears library in Python is used to implement CART and random for- est (RF) methods. XGBoost is implemented via their official package. The parameter values for these methods are set to default values, unless otherwise specified, such as the specific hyperparameters
21

---

tuning for RF and XGBoost discussed in Section 5.1 and Appendix J] The implementation of HHCART, RandCART and OC1 is adapted from publicly sourced GitHub repository and programmed in Python. We modified their ilasifiiation-ooriented loss functions to adapt for regression tasks.
As for the local search method ORT-LS, we reproduce it in Julia due to the absence of open-source code for ORT-LS. Aiming to provide reference for global training optimality, we also implement the MIP-based optimal oblique decision tree, ORT-MIP, in Julia, solving the MIP problem with Gurobi due to the absence of open-source code for ORT-MIP.
The GradTree, SoftDT, DGT and LatenTree methods are implemented using their respective open- source GitHub repositories, with adjustments made only to the epoch numbers to align with our methods. The TEL is implemented using their open-source code with their own default parameter settings, except for the number of trees and epoch numbers. We modify the epoch number to align with our experimental setup. Since it is tree ensemble method, we set the number of trees to 10.
Since no source code available for TAO-Linear, and the DTSemNet work directly uses the reported results from TAO-linear for comparison, we adopt the same approach to ensure consistency and credibility. DTSemNet itself a decision tree with linear predictions. For consistency, it also adapts the original DGT tree with constant predictions into linear variant, termed DGT-Linear. The datasets used in TAO-Linear are shared with DTSemNet and DGT-Linear, and DTSemNet directly collects the reported results from each method for comparison. Following their experimental setup, we apply the same data preprocessing, dataset splits and evaluation metric to implement our method on these five shared datasets. This allows for fair and direct comparison between our results and the summarized benchmarks presented in DTSemNet' Table 4, covering DGT-Linear, TAO-Linear, and DTSemNet itself. Detailed implementation settings for these baselines can be found in DTSemNet Panda et al. 2024). J. It is important to note that this, same-dataset comparison against TAO-Linear, DGT-Linear and DTSemNet, is the only experiment which we directly adopt the reported results for DGT (DGT-Linear), In our other experiments involving DGT, including Table 3 Section 5.2 and Table 22 Appendix K.10 we implement the experiments using their open-source code software.
Experiments necessitating CPU computation were executed on the HPC Cluster, specifically utilizing "Dell EMC R440 CPU" configuration. Each CPU job is allocated 32G memory with a Time Limit of 7 days. Experiments for ORT-MIP requiring larger memory resources were carried out on the Oracle HPC Cluster, specifically with 2T memory and 128 cores. Concurrently, experiments requiring GPU resources were conducted on the "Narval" server, with an NVIDIA A100 GPU equipped.
J Hyperparameters Tuning for Tree Ensemble Methods
For a fair comparison, comprehensive hyperparameter tuning is also performed for three tree ensemble methods. Regarding random forest RF, the number of trees in a forest is a critical parameter. It is well-recognized that testing performance improves with an increase in the number of trees; however,
the marginal gains become less pronounced as additional trees are added [Oshiro al. 201 Probst et al. 2019]. Accordingly, the number of trees is tuned across a set of (50, 100, 200, 300, 400, 500]. Moreover, the maximum tree depth is tuned over a broader range, from 1 to 50, to potentially capture optimal depth settings, given that RF empirically benefits from overly-deeper trees for enhanced testing accuracy. Other hyperparameters, including the number of features per split and the number of samples per tree, are maintained at default settings. These have been shown to balance the bias-variance trade-off, typically yielding robust performance with default values (Probst et al.) 2019).
For XGBoost, we follow the same hyperparameter tuning schemes, varying the number of trees across a set (50, 100, 200, 300, 400, 500), and the maximum tree depth from I to 50.
For the gradient- based tree ensemble TEL, no specific hyperparameter tuning is performed; we directly fix the number of trees to 10 and retain all other parameters at their default settings.
While our current hyperparameter tuning for tree ensembles, including those in Appendix K.6 with more-combination search for hyperparameters, is sufficient to support our main claims, espe- cially given that our goal is not to claim superiority over ensembles, more tuning on regularization parameters could potentially yield even better results for tree ensembles.
22

---

K
The Complementary Results of Numerical Experiments
K.1
Detailed testing accuracy comparison results medium-sized datasets in Group (i).
The testing accuracy (R²) comparison for various decision trees on specific 17 medium-sized datasets Group (i) detailed in Table 13
Table 13: Testing accuracy comparison for diverse decision trees on Group (i) 17 real-world datasets.
Greedy methods
Gradient-based Gradirree
Heurisitc Local Search
Our Optimized Tree
Datasets
CART
UC1
RandCART
INCART
SoftDT
CRT LS
RADDT
RADDT Linear
85.27
86.38
76.79
85.71
56.4h
67.06
85.24
90.34
90.65
40.53
50.70
49.05
30.47
47.46
49.51
59.46
61.20
3
47.29
46.15
46.94
54.75
49.68
55.28
$4.20
57.03
58.74
4
66.50
55.39
57.24
60.61
64.07
60.80
55.62
62.19
71.62
5 82.19
83,20
83.30
84.43
67.03
80.81
86.39
89.63
88.59
6 62.36
62.71
41.64
66.95
61.53
611.11
63.68
65.21
68.11
7 96.98
97.23
92.06
97.15
95.30
85.36
97.59
97.47
98.25
8 95.89
96.25
95.78
96.25
93.69
88.66
96.65
96.26
97.31
9 42.56
$1.53
51.83
56.32
44.22
71.60
69.57
81.26
86.23
10 60.19
59.03
58.42
60.91
54.76
62.76
$8.52
61.86
63.58
11 93.33
93.15
93.11
93.55
84.66
93.16
92.84
94.00
94.22
12 71.17
74.72
58.08
68.80
45.01
86.35
80.66
87.22
91.74
13
98.58
94.37
98.45
98.63
85.17
86.83
98.93
97.76
99.99
14 97.34
71.14
96.11
95.23
76.81
48.37
97.78
96.30
99.97
15
75.96
76.55
75.48
77.92
67.49
81.61
78.44
81.46
82.42
16
69.12 12
72.30
65.03
75.66
49.73
86.57
82.61
89.61
90.57
17
85.51
85.69
69.52
82.75
67.03
73.33
89.18
93.51
95.49
The testing accuracy (R²3) comparison for 3 tree ensembles specific 17 medium-sized datasets in Group (i) is detailed Table I4
Table 14: Testing accuracy comparison for three tree ensembles Group (i) 17 real-world datasets.
92.58
93.39
88.76
53.22
53.84
69.79
57.64
57.40
61.23
4
68.10
65.55
56.55
5
91.00
90.78
88.11
6
68.38
66.79
67.00
7
98.27
98.54
97.78
8
97.63
97.72
97.35
9
70.48
75.29
90.57
10
63.16
64.15
62.31
11
95.92
96.49
94.01
12
89.59
92.80
95.30
99.50
14
98.74
98.67
92.37
15
83.24
83,39
81.76
16
83.59
90.01
89.88
17
93.41
95.36
94.70
K.2
Implementation details of same-dataset comparisons for certain baselines
For GradTree, we follow their experimental setup: using 20% of the data for testing, macro F1- score evaluation metric, and averaging results over 10 runs with different random splits. Despite adhering to their dataset settings and hyperparameter configurations, we were unable to reproduce their reported results from Tables 1 and 2 in their paper. Therefore, directly compare our RADDT results with their published results.
Regarding soft decision tree, no tabular datasets were used in [Fosst and Hinton 201 but adopt the four tabular regression datasets from the original Soft Decision Tree study by IIrso et al. 2012] As specific dataset settings provided in that work, both Soft Decision Tree and RADDT.
default experimental setup for
Regarding TAO-Linear, DGT-Linear and DTSemNet, since no open-source code is available for TAD-Linear, and the DTSemNet work directly uses the reported results from TAO-Linear for comparison, adopt the same approach to ensure consistency and credibility. DTSemNet itself is
23

---

decisoin tree with linear predictions. For consistency, it also adapts the original DGT tree with constant predictions a linear variant, referred as DGT-Linear. Following DTSemNet's experimental setup, we apply the same data preprocessing, dataset splits (40% of the data for testing, unless otherwise specified for certain dataset) and evaluation metric (RMSE) to implement our method on the five shared datasets. This allows for a fair and direct comparison between our results and the summarized benchmarks presented in DTSemNet Taable 4, covering DGT-Linear, TAO- Linear, and DTSemNett itself. Detailed implementation settings for these baselines can be found in DTSemNet.
K.3 Detailed results for same-dataset comparison Group (ii) 27 datasets used by GradTree
Our same-dataset comparison for GradTree is performed on 27 of their original 36 datasets, with 9 excluded due to unavailability or ambiguity. Detailed dataset information is given in Appendix The result for each dataset is given in Table T5| using macro F1 Fl-score as the evaluation metric, following their original study. Our method outperforms GradTree by 4.99% on average in test performance.
Table 15: Testing comparison on 27 shared classification datasets Group (ii) with GradTree
Dataset Index
Dataset Name
Originally Reported Results in GradTree
Our RADDT
Gre-T
balance-scas
59.30
90.10
GradTree-2
manknote-authenticnn
98.70
99.70
Gra-Tree-3
blood-transfusion
62,80
66.00
4rudTree-4
cur-evaluation
44.00
86.80
GreeTree-S
congressional-voting
95.00
96.60
GradTreee 6
49.60
48.40
GradTrre-7
dermatology
93.00
94.40
GradTrce-8
echocardiogram iris
65.80
83.30
9
93.80
95.10
GradTree-10
sparmhas
90.30
92.10
GradTree-11
90.50
GradTree-12
wine
93.30
97.80
GradTree-13
adult
74.30
76.40
GradTree-14
bunk-marketing
64.00
GradTree-15
credit-card
67. 67.40
68.20
1radTree-16
gerrin
$9 19.20
66.10 10
GradTree-17
g glass
$6.00
58.20 28.20
GradTree-18
heart-failure
75.00
75.80
GradTree-19
landsat loan-house lymphography
80.70
86.30
GradTree-20
71 71.40
73 20
GradThee-21
61.20
GradTrce-22
mushrooms
100.00
100.00
GradTree-23
raisins
84.00
85.10
GradThee-24
segment
94.10
2radTree-25
solur-flare
15.10
15.40
GradTiee--26
wisconsin cencoosin--rrusttcc
90.40
94,80
GradTree-27
200
87.40
83.30
K.4 Detailed results for same-dataset comparison on Group (ii) 4 datasets used by soft trees
We provide the comparison results for each dataset in Table 16 The results show that RADDT outperforms the soft decision tree by 6.88% in testing accuracy (R), again aligning with prior results.
Table 16: Testing comparison on shared regression datasets in Group (ii) with Soft Decision Tree
Dataset Index
Dataset Name
Soft Decision Tree
RADDT
S
abalone
55.28
57.03
S
Puma8NH
60.31
65.21
Sof(Tree-3
computer
57.01
56.69
SoffTree-4
concrete
25.93
47.10
K.5 Detailed results for same-dataset comparison on Group (ii) 5 datasets used by DGT-Linear, TAD-Linear and DTSemNet
As earlier discussed in Section 5.1 we have compared our method with DCT-Linear, TAO-Linear and DTSemNet on the five shared datasets as used in the original work of DTSemNet. We extend DTSemNet's 's Table 4 by including results under the same experimental setup in Table 17
24

---

Table 17: Comparison on Group (ii) five datasets used by TAO-Linear, DGT-Linear and DTSemNet
Our RADOT-Limes
DTSenkiet
DGT-Linear
TAD-Linear
ROSE
Rank
RMSE
Rank
RMSE
Kank
RMSE
Rank
Abalone
1,984
1
2.135
2.144
2,07
Comp-Active
2.519
1
2.645
3
2.645
2.58
Ailerons
1.154
1
1.66
2
1.67
3
1,74
CTSlice
YearPred
11.934
8,99
1
9.02
2
9.08
Following DTSentlet work, trees with linear prediction are compared. 'These resulls are taken directly from DTSennlet's Table 4.
K.6 More extensive hyperparameter tuning for tree ensembles on Group (i) datasets
As previously indicated in Table 2 the findings of our methods being comparable tree ensembles RF and XGBoost are based on 300-combination specific hyperparameter tuning scheme. In that setting, our method is tuned only over tree depths from 1 to 12 with 12 combinations, ensuring much lighter tuning for fairness.
To further support this finding, extend the parameter search space to 5,400 combinations. This involves tuning the "tree depth" within a range of (1-50, 55, 60. 70, 80, 90, 100, 150, 200, 250, 300). "the number of trees" within (5, 10, 50, 100, 200, 300, 400, 500, 600, 700), and with the additional tuning for RF on "the minimum samples per leaf and per split" in (1, 2, 4), and for XCBoost "subsample" and "colsample_ betreee in (0.6, 0.8, 1.0]. Additionally, provide even stronger evidence, we further use PyCaret automated machine learning tool to perform an extensive 10.000-combination hyperparameter tuning for XGBoost, exploring its whole hyperparameter space with PyCaret's s default search settings.
As shown in Table 18, the 5, 4:00--comiinttionn tuning yields slight improvements in testing accuracy for both RF and XGBoost, with 0.11% 1% gain for RF and 0.26% gain for XGBoost over the 300-combination tuning in Table 2 The extensive 10.000-combination tuning for XCBoost via PyCaret leads just 1.04% gain. Despite extensive tuning, our key finding remains consistent: our single tree achieves accuracy comparable ensemble methods. Notably, ensembles, as any base learner including decision tree can be improved via ensemble techniques. Comparing single tree tree ensembles is inherently unfair. Instead, our goal is to showcase the potential of a single, optimized tree like ours in achieving high testing accuracy.
aim is not to claim superiority
tree
Table 18: Accuracy comparison on Group (i) datasets with extensive tuning for tree ensembles.
The Number Hyperparameter Tuning Combinations
Testing Accuracy (R',
RF (X00-comhination reported in Table
82.62
RF (5400-comtination)
82.73
XGBoost (300-combination reported in Table
83.51
XGBoost (5400-combination)
83.77
XGBoost l0000-combinatiinn PyCarct)
84.55
K.7 Detailed comparison against optimal trees on 4 small datasets in Group (iii)
As earlier discussed, ORT-MIP [Bertsimas and Dunn 2017 is computationally infeasible for previously-used datasets, even with 128 cores and a two-day time limit. It can only solve the 2-depth tree training problem on 4 small datasets in Group (iii) to a global optimum with 1 1% gap. Due to these limitations, only 50% samples are used for training in this experiment. Detailed training accuracy comparisons against ORT-MIP on these small datasets are presented in Table
Table 19: Train accuracy comparison results on solvable small datasets in Group (iii).
Dataset
Sample
Feature
ORT-MIP
RADDT
103
7
87.79
87.12
comcrete-slump-test-eee
103
89.89
84.92
hybrid-price
153
78.09
73.50
1pga-2008
157
86.79
85.73
Average Training Accuracy (Al 96)
85.64
82.82
Regarding the optimal sparse trees /Zhang et al. 2023). it complements earlier work on optimal trees (ORT-MIP) that fails to consider sparsity. As for experimental comparisons, optimal sparse trees
25

---

may not be directly comparable to our method. First, optimal sparse trees are limited to axis exis-aligned splits, which generally yield lower accuracy than oblique trees. Second, they are designed for binary features, requiring feature discretization that may degrade performance on our continuous-featue datasets. We therefore choose not to include this our experiments, as it could unfairly disadvantage their method under our evaluation setting.
K.8 Detailed comparisons against known ground truth on 3 synthetic datasets in Group (iii)
We provide the detailed comparison results for each synthetic datasct in Table 20 The known ground truths for both train and test accuracy are 100%. The results show that our RADDT closely approximate global optimality in train and test accuracy, with 0.64% difference over ground truth on average. These results, together with previous global solution comparisons, further validate the effectiveness of our tree optimization.
Table 20: Training and Testing performance on synthetic datasets in Group (iii).
Fitted Depth
Training Accuracy (I?", %)
Testing Accuracy (22", %))
Dataset
truth
RADDT
Ground truth
RADDT
Ground truth
KADDT
Syn-2
2
100
99,96
100
99.99
Syn-3
3
3
100
98.78
100
98.71
Syn-4
100
99.35
100
99.39
K.9
Ablation experiments on the strategies used our tree optimization
The observed superiority in training accuracy of our RADDT method can be attributed to two key strategies designed to enhance approximation accuracy, as discussed in Section 4 the multi-run warm start annealing strategy, and the strategy of adjusting initial solution for gradient- optimization. The comparative results, presented Table 2T] clearly illustrate the impact of these strategies on RADDT. It should be noted that our method, which utilizes the multi-run warm start annealing, is referred to as RADDT in the table. In contrast, when this strategy is not employed, the method is denoted by specific values of scale factors, such = 1 and a 150. Additionally, the strategy of adjusting initial solutions is evaluated the table, with the method labeled as RADDT without adjustments to initial solution and RADDT with adjustments to initial solution.
Regarding multi-run warm start annealing, we analyze training accuracy with and without this strategy. Without this strategy, we utilize fixed scale factors for comparison: a standard softmin function with small a = 1, and a larger scale factor a = 150. The findings indicate substantial improvements with the annealing approach: training accuracy increased by 9.7%, 9.32%, 8.46% and 1.07% at tree depths of 2, 4, 8, and 12, respectively, when compared to the standard softmin function without any scaling. Moreover, when compared to fixed scale factors larger than 1, the annealing strategy also yields higher training accuracy. These results confirm that our multi-run warm start annealing strategy is effective in enhaneing training accuracy, by striking greater balance between the approximation accuracy of scaled softmin function and the stability of gradient- praseeet-bbsed optimization.
The strategy of adjusting the initial solution for pradient-based optimization also contributes to these improvements. boosts training accuracy by 1.3%, 2.89%, 1.01% and 1.84% at tree depths of 2, 4, 8, and 12, respectively. Notably, these gains are achieved solely through improved initialization, without involving in the optimization process.
Table 21: The effectiveness of strategies used in our tree optimization approach on training accuracy.
Ite
D=2
D
D = 8
D = 12
without Multi-run Warm Start Annealing
(Standard Softmin Function)
60.78
69.97
81.46
93.45
(A fixed Scale Factor) with Multi-run Warm Start Annealing (Our RADDT method)
150
68.00
78.31
88.08
94.42
RADDT without adjustments to intial solution
70.48
79.29
89.92
94,52
RADDT with adjustments to initial solution
71.78
82.18
90.93
96.36
K.10
Scalability comparison on 7 million-scaae datasets in Group (iv)
In Section 5.3
we analyze the scalability of various methods on million-scale datasets in Group (iv)
under fixed-depth setting. The detailed results are presented in Table 22
26

---

Table 22: Scalability comparison under fixed-depth setting on 7 million-scale datasets in Group (iv).
Training Accuracy (It", %)
Testing Accuracy (JE", %)
Training Time (s)
Methods
14
DS
D12
D4
D8
D12
D8
D12
CART
24.18
35.19
42.06
47.80
23.91
34.99
41.35
41.57
17
25
RandCAKT
17.17
22.71
28.35
33.22
17.11
22.37
27.98
29.78
16
38
67
HECART
22.40
27.20
36.40
42.29
22.29
27.07
36.03
38,79
46
84
GradTree
19.67
26.92
33.36
19.48
26.60
33.16
1,387
3,058
14,570
SoftDT
18.19
27.36
28.36
18.13
27.24
28.21
136
16,263
DGT
30.26
35.27
30,10
34.99
202,537
232,574
TatentTree
40.04
39.74
RADDT 33.93
39.39
43.56
51.67
33,56
39.01
42.27
39.59
8,136
5,596
21,874
80,731
001 and ORT LS fail even at depit within 14 days. GradTree, SoftDT, DGT, and LatentTree face out of memory issues when scaling, GradTree and Do failing at depth 12, and DCT and LatentTree only solvable at depths 2 and
K.11 GPU-accelerated implementation for our RADDT experiments
Our differentiable tree is trained by solving an unconstrained optimization problem, offering substan- tial scalability benefits via its reformulated structure. Furthermore, by leveraging mature frameworks like PyTorcc, our implementation facilitates GPU acceleration, including distributed data parallel with multi-GPU. Under ideal full GPU utilization, training can also be distributed across multiple GPUs, further reducing time in proportion to the number of GPUs used. Concerning the training time reported Table 3 our RADDT method achieves superior accuracy without substantial in- crease in training time. While single-GPU acceleration is enabled for both our RADDT and other compared gradient-based trees, Our RADDT attains more efficient acceleration by fully leveraging matrix operation in computing our designed loss in Equation 7 which integrates unique tree path formulation. Specifically, by introducing the parameter Ug,,, we store the deterministic sample route and assignments in matrix to avoid loop-based calculation at every iteration, enabling efficient matrix operations for loss and gradient calculations. Additionally, for training 12-depth trees on Group (i) datasets with more than 10,000 samples, we use 4 GPUs to further accelerate RADDT.
Regarding scalability experiments on million-scale datasets reported in Table 22] we utilize 4 GPUs to train our RADDT at depths 2, 4, and 8, and 8 GPUs for depth 12. This distributed data parallelism is easily implemented using our extensible framework, which supports multi-GPU training through simple commands without requiring any specialized parallelization design.
K.12 Training time and speedup analysis on Group (i) datasets with over 10,000 samples
As in Table 3 our RADDT achieves superior accuracy without substantial increase in training time compared to other trees, such as the second-best ORT-LS. These scalability advantages become more pronounced when dealing with larger matrix operations, particularly involving in deeper trees or larger datasets with more samples and feature dimensions. To illustrate this, provide detailed comparison of training time and speedup for 12-depth tree training between RADDT and ORT-LS on the datasets with more than 10,000 samples in Group (i). The results summarized in Table 23
Table 23: The speedup of RADDT over ORT-LS for 12-depth tree training on Group (i) datasets with more than 10,000 samples.
Dataset Size
Feature Number
DRT L.
RADDT
Speedup
Dataset Index
Dataset Name
(p)
(Time,
(Time, s)
(ORT -L8/RADDD)
12
electrical deetrical-grii--aee grid--taaiee stability
10,000
12
197,361.31
1,691.10
116.71
13
condition-busede based- maased-maintenance compressor
11.934
16
232.929.77
2,036.77
114.36
14
condition- based maintenance, turbine
11,934
16
251,017.34
2.026.15
123.89
15
ailerons
13.750
40
965,968. 22
2,236.61
431.89
16
elevators
16,599
18
485,509 64
2,622.17
185.16
17
friedman artificial
40,768
10
671,460.77
4,331,58
155.02
K.13
Comparison our method's training time GPU versus CPU settings
In this section, we provide a comparison of our method's training time in GPU versus CPU settings, although the advantages of GPU acceleration are expected. We use fixed dataset, "sgemm-produet". with subsets varying sizes from (100, 1,000, 5,000, 10,000, 50,000) ) for training 8-depth and 12-depth trees. As expected, GPU training significantly faster. For instance, on 50,000 samples with an 8-depth tree, GPU training is 117 times faster than CPU. For 12 12-depth tree on 1,000 samples,
27

---

observe a 107 times speed-up. On larger datasets and deeper trees, the CPU version often fails to complete within days. This highlights the practical importance of GPU acceleration for scalability.
Table 24: Training time comparison of our RADDT method in GPU versus CPU settings.
Training Time (Secnnd)
S-depth treee
12-depth free
Datasize
One GPU
CPU
One GPU
CPU
100
337
615
769
10,912
1,000
359
2,938
1,043
111,111
5,000
466
22,082
2,799
OOT >5 days
10,000
614
46,132
5,057
OOT 25 days
50,000
2,949
345,992
41,564
OOT >5 days
Additionally, discussed in Appendix K.10 Appendix K. and Appendix K.12 also observed in this comparison, the GPU advantages become increasingly pronounced with larger matrix operations, particularly involving deeper trees, larger datasets with more samples and feature dimensions.
K.14 Interpretability analysis of our optimized tree
We fully agree that orthogonal trees like CART are more interpretable at the same, fixed depth. However, originally discussed in OC1 (Murthy et al. 1994). oblique trees become more interpretable when they require substantially less depth.
Our RADDT's interpretability can be assessed from three aspects: tree-based prediction logic, unique prediction path and the complexity of decision rules. First, RF, in Table using an average of 314.71 trees for higher accuracy, almost losing the interpretability for final predictions compared single tree. Second, our tree with ReLU-basee hard splits maintains a unique decision path leading to final predictions. These hard splits preserve the interpretability of True-False prcision-making which is often compromised in soft trees with a probabilistic path. Third, regarding the complexity of decision rules, oblique trees tend to generate smaller trees with clear oblique decision boundaries compared to orthogonal trees like CART. For example, using synthetic dataset "Syn-4" Table 20, CART achieves only 85.27% training accuracy for a 4-depth tree, whereas our RADDT attains 99. 99% for the same depth. To achieve a comparable train accuracy, CART requires deeper 9-depth tree with accuracy reaching 99.88%. Detailed results of CART under various depths given Table 23 CART with 9-depth tree results in complex, staircased boundary, shown in Figure 7 Such complexity can make decision rules difficult to interpret, whereas oblique trees with simpler and fewer splitting rules. makes our RADDT more interpretable despite the use of 2-feature combinations in tree splits. Notably, this example does not imply oblique holds better interpretability, but rather exhibit exclusive interpretability in certain datasets where underlying data distribution align with oblique boundaries.
1.00
1.00
0.75
0.75
Festure
0.50
0.50
0.25
0.25
0.00
0.00
1.00
0.00
0.25
0.50
0.75
1.00
Feature 1
Feature
(a) by 9-depth CART
by 4-depth RADDT
Figure 7: The decision boundary comparison for dataset "Syn-4".
Table 25: Train and Test accuracy for CART on synthetic dataset "Syn-4" under various tree depths.
Various Tree Depth
Ite
3
5
6
8
9
10
Training Accuracy (R', %)
27.65 25.91
56.86
73.39
85.27
92.41
96.49
98.20
99.61
99.88
99.96
Testing Accuracy (1E2 %)
54.23
71.67
80.65
84.36
87.04
87.93
87.83
87.75
88.19
28

---

When compared to other oblique trees as reported in Tad Table accuracy but also with a lower depth, such as our RADDT with depth of of 7.29 and RADDT-Linear with depth of 4.82. This reduction in depth significantly enhances interpretability with fewer rules. To illustrate, 2-depth tree yields 4 decision rules across 2 layers, whereas 10-depth tree produces 1024 rules across 10 layers. Understanding hundreds of nested IF-THEN rules can be challenging.
our methods achieve superior
Additionally, as in Table our methods can achieve slightly better accuracy than CART with signifi- cantly smaller trees: average depths of 2.82 (RADDT) and (BADDT-Linear), compared to 10.24 for CART, leading to 30-80 times fewer parameters. In this case, for example, 1-depth tree consists of only 2 leaf nodes with 2 rules, which is highly interpretable because we can explain model predictions as "IF the feature combination is less than a threshold, THEN the prediction is based on the left leaf node; otherwise. right leaf node." These results highlight oblique tree's 's ad advantages in higher accuracy with smaller depth, typically yielding less prediction rules and fewer model parameters.
Therefore, interpretability depends on multiple factors including tree depth, feature number, and the iccuracy-simplicss trade-off. There is no interpretability superiority of one approach over the other, as it depends on specific application scenarios.
K.15 Overfitting issue and comparison for trees with linear predictions
As discussed in Section 5.6 overfitting issues have been observed with both our RADDT and RADDT-Linear method. Upon further comparison of our RADDT-Linear with the existing open- source library tree, it is evident that the overfitting issues are more pronounced in trees with linear predictions. The open-source software linear-tae -treeerreeeeeeee exhibits significantly more severe overfitting issues at depths such 8 and 12, detailed in Table 26
For our RADDT-Linear, although the training accuracy improves by 6.52% from depth 4 to 8, testing accuracy conversely drops by 9.67%, indicating serious overfitting issue. To mitigate the overfitting issues for
we preliminarily attempt to apply L1 regularization to trainable variables A. This approach involves incorporating regularization term into the loss function L below, serving to penalize the complexity of the tree structure. The regularized loss is delineated in Equation (8). where X denotes the regularization strength and
|| represents the L1 norm.
However, identifying the appropriate regularization strength proves to be challenging during our experiments, necessitating extensive hyperparameter tuning. This tuning significantly increases the computational cost and the implementation complexity of our method. Consequently, in our experiment reported in Table 2 we did not tune this parameter. We just use very small value le 4 to implement a minimal regularization, aiming to enhance testing accuracy without greatly compromising the optimization capabilities. With this slight regularization, the testing accuracy of RADDT-Linear reported in Table 2 is improved by 0.58% compared to the results without regularization, as shown in Table 27 Despite the slight improvement, the overfitting issues for RADDT-Linear still exist, and our preliminary regularization is not sufficient to address this issue. Significant improvements in testing accuracy achievable through appropriate regularization strategies; however, this requires further exploration and is limited in this paper.
Table 26: Comparison of training and testing accuracy for RADDT and tieear-tree.
Training Accuracy (If", %)
Testing Accuracy (R,, %)
Depth
linear tree
RADDT Linear
linear tree
RADDT Linear
79.85
82.92
79.46
81.74
85.47
86.73
73.58
83.10
93.33
93.25
-376648.8 84 (overfitting)
73.43
98.31
-11288345.94 94 (overfitting)
38.98
Greg
S(U,)) (y: - (KT + h1)))²
+
Σ tETs
||alll
(8)
Table 27: The comparison for RADDT-Linear with and without regularization across 17 datasets.
Ttem
RADDT-Lineat Linear without regularization
RADDT-Linest Linear with regularization
Testing Accuracy (R² %)
84.05
84.63
29

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims the abstract and introduction accurately reflect the paper's contributions, including the proposal of novel decision tree formulation with demonstrated accuracy and scalability benefits, as supported by our experimental results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations our work are explicitly discussed in Section 5.6 with
experimental discussions in Appendix K.15
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
30

---

Answer:
[NA]
Justification:
This work does not include theoretical proofs and results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proof's provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide full details of our model architecture with a novel decision tree reformulation in Section training procedures in Algorithm [T] hyperparameters analysis in Appendix F and evaluation metries. The datasets used are publicly available detailed in Appendix H and reproduction scripts are provided in GitHub repository. Together, these materials ensure that experimental results can be reproduced.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
31

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification; The datasets used are publicly available from UCI and OpenML, as detailed in Appendix H We provide open access to the source code of our method via GitHub reposi- tory, along with detailed instructions run the code and reproduce the main experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
SCodee/mmddsbmbim SontdeeSubmsssioPooo...oooo ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All experimental settings are clearly specified in the paper. Dataset usage, data splits and hyperparameter selections are described Appendix a[d Appendix De- tailed experimental procedures and algorithm configurations are also provided in Appendix] ensuring the results can be fully understood and interpreted.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: In addition to reporting performance metrics in comparison tables, we conduct paired T-tests to assess the statistical significance of our results. This analysis provides further support for the validity of our comparisons, given in Section 5.1
32

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide detailed information about the compute resources used for our experiments, detailed in Appendix !
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported didn't ' make it into the paper).
paper (e.g., preliminary or failed experiments that
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics htttpe////oorrpss.c////lll//sess
Answer: [Yes]
Justification: We have reviewed the NeurlPS Code Ethics and confirm that our research fully complies with its principles.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
33

---

Answer:
[NA]
Justification: This work focuses on foundational advances in differentiable decision tree learning and is not tied any specific application with immediate societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This work does not involve models or datasets with high risk of misuse, and thus specific safeguards are necessary.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The datasets used are clearly cited originating from UCI and OpenML. All baseline code sources are properly credited and detailed in the paper.
Guidelines:
The answer NA means that the paper does not existing assets.
34

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license ge.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, pappessiithheeeocc thoode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-pane re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We release our reproduction code as new asset under an open-source license via GitHub repository. The code is well documented, with clear instructions and usage details provided.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
35

---

Justification:
The work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
36


Reviews:
[{"review_id": "jIa82CgTK5", "reviewer": "Reviewer_pLD8", "summary": "- This paper proposes a gradient-based learning method for oblique decision trees.\n- It first exactly reformulates the problem of learning hard-split oblique trees into an unconstrained optimization problem, minimizing a loss function constructed using the ReLU function and the argmin operator. Next, it introduces a surrogate loss by replacing the argmin operator with a differentiable softmax function, and then learns the tree using a gradient-based method.\n- Numerical experiments demonstrate that the proposed method yields decision trees with higher test accuracy compared to existing gradient-based decision tree learning approaches.", "questions": "- Regarding the first weakness I raised: Does the proposed method still achieve better accuracy on the training data compared to existing methods, even without using the warm-start annealing strategy for both? Please point out if I've overlooked any experimental results addressing this.\n- Concerning the ReLU-based cumulative violation: If $a_j$ and $b_j$ are  zero for all $j$, then $v_{i,j}$ is zero for all $j$. In this specific case, the unique path might not be determined by Eq. (4). While this may be a corner case, I am interested in whether such a scenario could cause any practical or numerical issues during the training process. \n- The motivation for using simulated annealing to adjust $\\alpha$ isn't entirely clear to me. As $\\alpha$ increases, the surrogate loss (6) approaches (5), so from the perspective of minimizing (5), it would be reasonable to set $\\alpha$ as large as possible (assuming numerical stability issues don't arise). From this viewpoint, couldn't a binary search-like approach be more efficient for adjustment than simulated annealing?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "- Strengths\n\t- Decision trees are widely used as highly interpretable predictive models, and the proposed computationally efficient learning algorithm for decision trees holds significant value in the field of machine learning.\n\t- The research motivation is clear, and the proposed method is explained in an understandable manner.\n\t- The computational experiments are comprehensive. Notably, the validation of effectiveness through variance testing is commendable. Furthermore, it's interesting that the optimization in training leads to improved accuracy compared to existing gradient-based learning methods.\n\n- Weaknesses\n\t- The proposed method's performance is significantly improved by a multi-run warm-start annealing strategy. While this isn't inherently problematic, it makes it difficult to ascertain whether the effectiveness of the proposed method, relative to prior gradient-based decision tree learning research, is fundamentally due to the ReLU-based reformulation itself.\n\t- The numerical experiments show that the proposed method can obtain trees with lower loss on training data than existing gradient-based approaches. However, the theoretical insights from a mathematical optimization perspective as to why such results are obtained are somewhat limited.", "was_revised": true, "final_justification": "The authors have sincerely addressed all of my concerns and questions. While I recommend they revise the manuscript to incorporate these points, I believe the paper is suitable for publication.", "rebuttal": "We sincerely appreciate the reviewer's recognition of our work, as well as the constructive feedback provided. These comments are highly valuable and have helped us improve the clarity and completeness of our manuscript. Below, we carefully address each of the concerns and questions raised.\n\n\n>**Q1-\"Regarding the first weakness I raised: Does the proposed method still achieve better accuracy... even without the warm-start annealing strategy? Please point out if I've overlooked any experimental results addressing this.\"**\n\nThank you for your important attention to the annealing strategy. In our manuscript, we provide an ablation study demonstrating its effectiveness at the end of Section 5.2 and in Appendix K.7.\n\nWithout the annealing strategy, training accuracy drops significantly, especially when using the standard softmin without any scaling (i.e., $\\alpha=1$). Specifically, as reported in Appendix K.7, Table 19. Training accuracy with $\\alpha=1$ is 9.7%, 9.32%, and 8.46% lower than with annealing at tree depths of 2, 4, and 8, respectively. This decline is due to the large approximation gap introduced by the standard softmin function, as illustrated in Appendix F, Figure 6.\n\nEven without annealing, the issue can be partially mitigated by increasing the softmin scale factor $\\alpha$. This intuitive adjustment does increase performance; for instance, setting $\\alpha = 150$ improves training accuracy by 7.22%, 8.34%, and 6.62% over $\\alpha = 1$ at the respective depths. However, it still underperforms compared to annealing, likely because $\\alpha = 150$ is not optimal. Increasing $\\alpha$ helps to reduce this gap, but excessively large values can lead to numerical instability. Therefore, simply increasing $\\alpha$ is not a reliable solution. For reference, the results from the manuscript are summarized below:\n\n|  | D=2|D=4|D=8|\n|-|-|-|-|\n|$\\alpha=1$ (Standard Softmin Function)|60.78|69.97|81.46|\n|$\\alpha=150$|68.00|78.31|88.08|\n|With Our Annealing|70.48|79.29|89.92|\n\nTherefore, scaling the softmin with an appropriately chosen $\\alpha$ can improve accuracy even without the annealing strategy. However, identifying the optimal $\\alpha$ is challenging. Our annealing strategy is specifically designed to address this challenge by dynamically balancing approximation quality and stability throughout training. We will further discuss its effectiveness in response to your Q3 below.\n\n>**Q2-\"Concerning the ReLU-based cumulative violation: If $a_j$ and $b_j$ are zero... while this may be a corner case, I am interested in whether such a scenario could cause any practical or numerical issues during the training process.\"**\n\nThank you for your insightful comment on this corner case. Indeed, if both $\\mathbf{a}_j = \\mathbf{0}$ and $b_j = 0$, it provides same violations for all leaves, which could impair the training process.\n\nWe address a similar case in Section 4.2, where we discuss the impact of initialization and introduce an adjustment strategy to handle cases where $\\mathbf{a}_j^T \\mathbf{x}_i - b_j = 0 \\approx 0$. However, in the specific scenario you raise, when $\\mathbf{a}_j = \\mathbf{0}$ and $b_j = 0$, this adjustment also becomes ineffective. We acknowledge that this is a limitation of the current implementation. To mitigate this, we typically use random initialization to avoid such worst-case scenarios.\n\nFortunately, based on our extensive experiments, such cases appear to be extremely rare in practice, and we have not observed noticeable performance degradation due to this issue. We appreciate you pointing it out and will explicitly mention this limitation in the revised manuscript.\n\n>**Q3-\"The motivation for using simulated annealing to adjust $\\alpha$ isn't entirely clear to me. AS $\\alpha$ increases, the surrogate loss (6) approaches (5), it would be reasonable to set $alpha$ as large as possible (assuming numerical stability issues don't arise). From this viewpoint, couldn't a binary search-like approach be more efficient for adjustment than simulated annealing?\"**\n\nThank you for your valuable comment regarding the annealing strategy. Following our response to your Q1, we would like to clarify the motivation behind using annealing for adjusting $\\alpha$.\n\nBinary search provides a more structured way to explore different $\\alpha$ values for scaling the softmin approximation. Unlike random trials, it narrows the search range by evaluating performance at the midpoint and adjusting boundaries accordingly. While this is more principled than random guessing, it still involves testing isolated $\\alpha$ values. As discussed in the response to your Q1, this approach does not match the performance of our annealing strategy.\n\nWhile we agree that a binary search-like approach can be used to identify an effective $\\alpha$, our empirical results show that gradually increasing $\\alpha$, rather than directly using a large fixed value, leads to better training outcomes. This is because starting with a smaller $\\alpha$ allows the model to optimize under a smoother case, improving stability. As $\\alpha$ increases, it becomes sharper and closer to the ideal formulation, and the model benefits from being progressively adapted to this more accurate approximation. Our annealing strategy takes advantage of this effect by warm-starting each successive optimization task with the solution from the previous task with smaller $\\alpha$. This gradual refinement enhances the approximation accuracy, while mitigating numerical instability typically associated with larger $\\alpha$. \n\nTo further address your concern, we conducted a direct comparison between our annealing strategy and a binary search, using the same number of optimization runs and the same $\\alpha$ search range. Specifically, our annealing strategy performs 5 optimization tasks, each with a different $\\alpha$ value sampled in log-space within a predetermined range. For a fair comparison, the binary search also performs 5 sequential optimizations, where each $\\alpha$ is selected via bisection within the same range. The binary search is implemented by starting at the midpoint of a given range as the initial scaling factor for the optimization. It then iteratively narrows the range by evaluating performance at the midpoint and updating one boundary accordingly. This process continues for five iterations, resulting in five optimization runs with five successive bisections.\n\nThe average training accuracy across 17 regression datasets for different tree depths is summarized below. Our annealing strategy consistently outperforms binary search, with an average improvement of 2.82% across all depths.\n\n|Depth|2|4|8|12|\n|-|-|-|-|-|\n|Binary Search|69.95|77.33|87.69|94.98|\n|Our Method|71.78|82.18|90.93|96.36|\n\nThese results empirically validate the effectiveness of our annealing strategy in practice. However, we acknowledge that this finding is based on empirical observation, and a theoretical analysis is still lacking. We will include this discussion and its limitation in the revised manuscript."}, {"review_id": "ehA4RvVEix", "reviewer": "Reviewer_ZgpM", "summary": "This paper introduces a novel differentiable decision tree method called RADDT, leveraging a \"ReLU+Argmin\" formulation. The key contributions include addressing non-differentiability issues through ReLU functions combined with an approximated argmin operation via scaled softmin. Additionally, the authors introduce a multi-run warm-start annealing strategy to enhance training stability. Empirical results demonstrate substantial accuracy improvements compared to baseline methods.", "questions": "Q1: [3] proposes a method to handle soft decisions in decision trees. What advantages does your method have over [3], and why was this comparison omitted?\n\nQ2: What advantages does your method provide compared to selecting the path with maximum probability, as proposed by [4]?\n\nQ3: RADDT significantly outperforms standard SDTs. What happens when the ReLU+Argmin approach is removed, and a standard STD is trained using your advanced training protocol?\n\nQ4: Could an entmax-like transformation be utilized for your softmin operation to ensure smoother gradients?\n\n---\n\n[3] Norouzi, Mohammad, et al. \"Efficient non-greedy optimization of decision trees.\" Advances in Neural Information Processing Systems 28 (2015).\n\n[4] Frosst, Nicholas, and Geoffrey Hinton. \"Distilling a neural network into a soft decision tree.\" arXiv preprint arXiv:1711.09784 (2017).", "limitations": "No, see weaknesses (specifically regarding interpretability).", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n- **Novel ReLU Formulation**: The use of ReLU and argmin for differentiable decision trees is innovative and, to the best of my knowledge, novel.\n- **Multi-run Annealing Strategy**: The proposed annealing method appears novel and shows a significant impact on performance in the ablation study.\n\n---\n\n## Weaknesses\n\n### Major Weaknesses\n\n- **Confusion Between Axis-Aligned and Oblique Trees**:\n  - The paper mixes standard (axis-aligned) and oblique decision trees, potentially confusing readers.\n  - Comparisons with CART, RF, and GradTree (especially in the abstract) lack clear explanation of fundamental differences. Performance gains over CART are unsurprising given the significantly higher complexity of oblique splits.\n  - Tables only categorize by optimization method, obscuring the types of decision trees compared (axis-aligned vs. oblique). This is particularly problematic when comparing complexity in terms of tree depth (Tables 1 and especially 2). Axis-aligned DTs consider only one feature per split, whereas oblique DTs consider linear combinations of features. For instance, the ailerons dataset has 40 features, significantly affecting complexity and making tree depth a poor proxy. An alternative measure, such as parameter count, should be added. Additionally, CART trees are typically not fully-grown to their maximum depth, a factor not currently considered.\n  - The abstract, introduction, and conclusion emphasize interpretability of standard trees, yet the proposed method is oblique without adequately discussing interpretability implications.\n  - The scenarios presented in Appendix A not only argue in favor of hard decisions, but also—at least implicitly—support axis-aligned splits. For example, the discussion of pressure exceeding a threshold clearly suggests a univariate (i.e., axis-aligned) split, which cannot be directly modeled using oblique splits. This stands in contrast to the proposal of hard yet oblique decision trees, and again introduces confusion.\n\n- **Improper Hyperparameter Optimization (HPO)**:\n  - Hyperparameters for baseline models (CART, RF, especially XGBoost) are not adequately tuned, violating standard scientific practice for tabular data.\n  - Claims of beating XGBoost without thorough HPO are misleading.\n\n- **Interpretability Analysis**:\n  - I strongly disagree with the interpretability analysis in its current form. IF-THEN rules typically mirror human decision-making closely (see e.g. [1]). Oblique trees have inherently lower interpretability at individual splits, especially when not sparse—and no sparsity is demonstrated. Making interpretability claims without proper analysis, particularly on real-world datasets, is highly problematic.\n\n### Minor Weaknesses\n  - In Section 4.3, the phrase \"optimal solutions\" could be misunderstood in the context of optimal decision tree literature; a more careful wording is suggested.\n  - Alternative metrics such as ROC AUC, MAE, and MSE are missing. Accuracy alone is insufficient; including these (at least in the appendix) would strengthen the evaluation.\n  - The authors use reinforcement learning as an example where non-differentiability remains a major barrier, but methods already exist addressing this issue using gradient-based decision trees (see [2]).\n\n---\n\nWhile my review may come across as quite critical, this is directed at the current state of the paper rather than the underlying idea, which I find promising. If the authors are able to address the concerns raised, I would be happy to revise my score. However, in its present form, I see several substantial issues.\n\n---\n\n[1] Hastie, Trevor, Robert Tibshirani, and Jerome Friedman. \"The elements of statistical learning.\" (2009).\n\n[2] Marton, Sascha, et al. \"Mitigating information loss in tree-based reinforcement learning via direct optimization.\" (2025).", "was_revised": true, "final_justification": "This paper presents a novel differentiable decision tree method based on a ReLU+argmin formulation, combined with an annealing training strategy, and shows promising empirical results along with open-sourced code. The authors provided a detailed and thoughtful rebuttal that addressed the most critical issues raised in the initial review. In particular:\n\n- The confusion between axis-aligned and oblique trees was clarified, and the authors agreed to make this distinction explicit in the revised paper.\n- Concerns regarding hyperparameter optimization (HPO) were addressed with extensive tuning experiments. While I believe more recent tuning practices (e.g., for XGBoost) could still be adopted, the current results are sufficient to support the paper's claims.\n- The interpretability discussion was expanded and contextualized better, particularly with respect to depth and rule complexity.\n- The authors acknowledged additional prior work and agreed to include appropriate citations and clarifications.\n\nOverall, the revised paper will be significantly strengthened, and I believe it can make a contribution to the field.", "rebuttal": "We sincerely thank the reviewer for their effort in evaluating our work and for the thought-provoking questions. We address each point in detail below.\n\n\n> **Q1-\"Confusion between axis-aligned and oblique trees\"**\n\n> Q1-1 \"Comparison with CART RF and GradTree lacks explanation. Performance gains over CART are unsurprising...\"\n\nThank you for pointing this out. We appreciate the suggestion and will include the clarification in the revision.\n\nOur primary focus is on comparing oblique trees. Among the 14 baselines, all are oblique except for CART, RF, XGBoost, and GradTree. We include CART as a widely recognized foundational method. Its inclusion aligns with prior work on oblique trees, such as TAO (Zharmagambetov and Carreira-Perpinan, 2020), DGT (Karthikeyan et al., 2022), DTSemNet (Panda et al., 2024), TEL (Hazimeh et al., 2020), which also compare against CART. Although outperforming CART is expected, its inclusion helps quantify the amount of improvements achievable by oblique tree.\n\nGradTree is included as a representative gradient-based tree using STE, enabling fair comparison against other STE-based oblique trees like DGT and DTSemNet.\n\nSince it remains uncertain whether oblique trees can match ensemble's accuracy, we include RF as a commonly used and strong ensemble baseline, and TEL as the oblique ensemble counterpart in our comparisons.\n\n> Q1-2 \"Alternative parameters count, should be added.\"\n\nThank you for valuable suggestion. We agree that parameter count offers a clearer view of model complexity. While oblique tree typically require more parameters at a given depth, it often yields better accuracy with much smaller depth. **Thus, for similar accuracy, oblique tree may not require more parameters overall**.\n\nFor a D-depth tree with $T_B=2^D-1$ branch nodes and $T_L$ leaf nodes and p input features:\n- Axis-aligned tree requires $T_B *2 + T_L$ parameters.\n- Our GET uses $T_B * p + 1 + T_L$ parameters.\n- Our GET-Linear uses $T_B * p + 1 + T_L * p + 1$ parameters.\n\n\nFrom Tables 1 and 3, CART achieves 74.85% accuracy with average depth 10.24 and ~3,141 parameters. GET and GET-Linear reach 82.39% and 84.63% accuracy at depths 7.29 and 4.82, using ~10,504 and ~4,045 parameters, respectively. Notably, if the goal is to match or slightly exceed CART's accuracy, our models can do so with much smaller trees. Our new experiments show that GET achieves 75.23% at depth 2.82 using only 101.71 parameters, and GET-Linear reaches 77.21% at depth 1 with just 40.47 parameters, **yielding 31× and 78× reductions in parameter count compared to CART**.\n\n|Method (Accuracy)|Depth|Number of Branch Nodes|Number of Leaf Nodes|Total Number of Parameters|\n|-|-|-|-|-|\n|CART (74.85)|10.24|1,046.65|1,047.65|3,140.94|\n|GET (82.39)|7.29|671.94|672.94|10,503.94|\n|GET-Linear (84.63)|4.82|129|130|4,044.71|\n|GET (75.23)|2.82|6.88|7.88|101.71|\n|GET-Linear (77.21)|1|1|2|40.47|\n\n> Q1-3 \"CART are not fully-grown to maximum depth.\"\n\nThank you for highlighting this point. A fully-grown CART, expanded until all leaves are pure as in default sklearn setting, are rarely used in practice due to overfitting and reduced accuracy. In this regard, we tune CART's depth from 1 to 100. This 100-depth search is sufficient to identify its optimal depth. For reference, a fully-grown CART leads to an average test accuracy drop of 9.27% compared to our tuned version reported in Table 1.\n\n>**Q2-\"Improper HPO. Hyperparameters are not adequately tuned\"**\n\nThank you for your thoughtful comments. We would like to clarify that we have carefully tuned hyperparameters for RF and XGBoost, as detailed in Section 5.1 and Appendix J. Our tuning follows the guidelines from Oshiro et al. (2012) and Probst et al. (2019), which emphasize the importance of tuning the number of trees and tree depth. We tune the number of trees from {50, 100, 200, 300, 400, 500} and depth from 1 to 50, while keeping other parameters at default values as recommended.\n\nThis setup yields 300 tuning combinations for both RF and XGBoost. In contrast, our method is tuned only over tree depth from 1 to 12 (12 combinations), ensuring a much lighter tuning for fairness. To further address your concern, we extend the search to 5,400 combinations: depth in {1–50, 55, 60, 70, 80, 90, 100, 150, 200, 250, 300}，number of trees in {5, 10, 50, 100, 200, 300, 400, 500, 600, 700}， with additional tuning for RF (min samples per leaf and per split in {1, 2, 4}), and for XGBoost (subsample and colsample_bytre in {0.6, 0.8, 1.0}). \n\nThese 5,400-combination yield slight improvements: +0.11% for RF and +0.26% for XGBoost over the 300-combination. We further use PyCaret library to perform an extensive 10,000-combination HPO for XGBoost across all its hyperparameters, leading to just a 1% gain. A summary is given below:\n\n|Method|Tuning Combinations|Accuracy|\n|-|-|-|\n|RF|300|82.62|\n|RF|5,400|82.73|\n|XGBoost|300|83.51|\n|XGBoost|5,400|83.77|\n|XGBoost|10,000 (by PyCaret)|84.55|\n|Our GET|12|82.39|\n|Our GET-Linear|12|84.63|\n\nDespite extensive tuning, our key finding remains unchanged: our single tree achieves accuracy comparable to ensemble methods. The statistical Friedman rank further shows no significant difference, as XGBoost shares the top rank with ours. \n\nImportantly, our aim is not to claim superiority over ensembles. Since any base learner can be improved via ensembling like bagging, comparing a single tree to ensembles is inherently unfair. Instead, we aim to provide a reference showing that our tree can match ensemble's accuracy with far fewer parameters.\n\n>**Q3-\"Interpretability\"**\n\nThank you for your insightful comments. We fully agree that, at the same depth, axis-aligned trees like CART are more interpretable. However, as originally noted in OC1 (Murthy et al., 1994), oblique trees could become more interpretable when their depth is substantially smaller.\n\nFor example, as shown in Appendix K10, on a synthetic 2-feature dataset, our method yields a depth-4 oblique tree with 16 rules, whereas CART requires depth-9 with 512 rules. Despite using 2-feature combinations, the much smaller depth improves interpretability. Similarly, as noted in Q1-2, our models can also achieve slightly better accuracy than CART with  much smaller depths: 2.82 (GET) and 1 (GET-Linear) compared to 10.24 for CART, leading to 30–70× fewer parameters.\n\n>**Q4-\"minor weaknesses\"**\n\n> Q4-1 \"Alternative metrics such ROC AUC are missing.\"\n\nThank you for your suggestion on additional metrics. For same-dataset comparison on Group (ii) datasets, we adopt the same metrics used in the original works we compared with: RMSE for DTSemNet, DGT-Linear, and TAO-Linear, and F1-score for GradTree. For other experiments, we mainly report accuracy and Rank. We agree that additional metrics can offer a more comprehensive evaluation and will incorporate them in the revision.\n\n> Q4-3 \"reinforcement learning... but method already exists like (Marton et al., 2025).\"\n\nThank you for bringing this excellent study to our attention. We will cite it in the revision. It adopts GradTree (Marton et al., 2023) to learn decision tree policies, a method we already included in our comparisons.\n\nWhile both methods are gradient-based, they differ in formulation and optimization. Their approach uses axis-aligned trees with STE, offering efficiency for certain tasks, whereas ours focuses on oblique trees with differentiable approximations, yielding strong empirical performance. We view these two work are complementary with different applicability, and will clarify this distinction in the revision.\n\n>**Q5-\"Other questions\"**\n\n> Q5-1 \"(Norouzi et al., 2015) proposes a method to handle soft decisions. What advantages does your method have, and why was this comparison omitted?\"\n\nThank you for bringing this important work to our attention. Norouzi et al. (2015) introduce a surrogate loss to enable optimization. In contrast, our method uses an exact reformulation of classic tree with a different optimization. These represent two distinct approaches. Due to the lack of public code and the table-based results in their paper, a direct comparison was not feasible. We will cite this work and clarify the distinction in the revision.\n\n> Q5-2 \"What advantages do your method provides over SDT (Frosst and Hinton, 2017)? What happens if a SDT is trained using your advanced training protocol?\"\n\nThank you for your insightful comments. We have included SDT in our manuscript. SDT uses a sigmoid function to approximate hard decisions, resulting in probabilistic paths. However, these approximations accumulate across all nodes, potentially degrading accuracy in deeper trees. In contrast, our method is based on an exact reformulation. Its superiority can be attributed to our loss formulation and optimization strategies like annealing.\n\nRegarding applying our training protocol to SDT, we agree this is an interesting direction. However, effects are difficult to predict without extensive experiments. While our strategies may help mitigate approximation issues for smaller trees, deeper trees may still suffer from accumulated errors. For instance, even with a strong sigmoid output of 0.9 per node, the path probability at depth 10 becomes $0.9^{10}=0.35$ (in worse case of $0.55^{10}=0.003$), leading to poor sample assignments. In our current experiments, we use the original SDT code from GitHub without modification for fair comparison. We will further explore applying our training strategies to SDT and include this in the revision.\n\n> Q5-3 \"Could an entmax be utilized for your softmin operation?\"\n\nThank you for this thoughtful suggestion. Entmax, as used in GradTree (Marton et al., 2023), generalizes softmax by allowing sparse outputs controlled by a scalar, recovering softmax at 1 and producing exact zero at 2. Given its similarity to our scaled softmin, we agree that entmax is a promising alternative. However, selecting a sparsity parameter is challenging. We will explore this and discuss it in the revision."}, {"review_id": "VVwRkHOWSk", "reviewer": "Reviewer_oByt", "summary": "This paper introduces RADDT, a binary differentiable tree which uses oblique decisions. This model leverages differentiability in two steps: (i) it describes paths by counting the number of rule violations through relu functions (where a null output means a correct path) and (ii) it uses a softmin function to mimick the argmin operator for identifying the unique path leading to a decision. The model shows competitive performances to 14 (non-)differentiable trees with regards to both classification and regression tasks on an extensive benchmark of 67 datasets.", "questions": "Following the points highlighted in weaknesses, here are the isolated questions:\n\n1. Could the authors mitigate the cost of their accuracy improvements depending on the number of parameters compared to other models?\n2. Could the authors provide better insight on the training time specifically depending on the number of samples, features and tree depth?\n3. Could the authors further detail the nature of the initialisation SVM and how frequently and harmful degenerate cases happen?\n4. What are the authors' stance on the interpretability of their (non-sparse) oblique tree when depth, a user-defined hyperparameter, exceeds 5?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n+ *The paper is overall well-written*. It is easy to follow, and I found the mathematical notations quite clear.\n+ *The benchmark is commendable*. The number of compared models (14) and the number of datasets (67) subdivided into 4 different categories clearly substantiate the claim of RADDT's performance. In addition, the appendix clearly contributes to enriching the results and completes well the main section.\n+ *Appropriate appendices*: It turns out that most of my questions were already addressed by the appendix when reading the paper. From this criterion, I think that the appendices complement well and support the entire paper appropriately.\n+ *The model is intuitive to implement*. At the end of the paper, it seems that the model can be interpreted as a typical MLP with RELU activation where each layer is twice as big as the preceding one (thus expanding the tree in breadth). This MLP has one fewer layer than the desired depth, and the softmin operator then serves as a key indicator of which prediction parameters should be retrieved from a look-up table. Though subjective, this second reading could perhaps contribute to the understanding of the performance for the authors.\n\n**Weakneses**\n\nDespite the mertis previously listed, few items remain unsolved in my opinion:\n\n+ *The discussion on the number of parameters is somewhat limited*. From the introduction, the authors argue that oblique trees are \"[a]iming for higher accuracy with fewer parameters\", and similarly that they \"tend to generate smaller trees [...] compared to orthogonal trees like CART.\" (Appendix K.10). While I acknowledge that an oblique decision compensates for multiple orthogonal decisions, I find that quite confusing as the depth seems to be a user-defined parameter in oblique tree, as especially shown in experiments with arbitrary depth set to 12. In addition, since all nodes use linear decision, the number of parameter seems to be $(2^D-1+2D)(d+1)$ for $d$ features and depth $D$ in a regression task, which can be quite expensive for a large number of features, or even some deep trees. Could the authors mitigate the cost of their accuracy improvements depending on the number of parameters compared to other models? In line with this comment, I believe that a discussion on the training time specifically depending on the number of samples, features and tree depth would enhance the trade-off rationale for selecting RADDT as a model in future tasks.\n+ *Discussion on initialisation could be improved*. The authors acknowledge that initialisation is crucial to their decision tree, and devise local schemes based on maximum margins to between samples. However, this section (4.2) seemed insufficiently clear. The binary classes are not specified for training each SVM per node of the tree. Moreover, it seems that the corner case where all the training dataset ends up in a single unique path is not considered.\n+ *Few missing references*. In this paper, authors consider only differentiability through the prism of oblique trees. Yet the literature as also shown alternative ways of definining it, e.g. [1]. In addition, I think that [2] is absent from the discussion, even though it defines *sparse* oblique trees and seem quite appropriate to the scope of the paper.\n+ *Some additional discussion on interpretability would be welcome*. in line with the sugestion of [2], it seems a bit unconventional to read a paper on decision trees, yet have most of the interpretability put away in the appendix (K.10). Although the authors clearly ague that there are interpretatbility benefits in terms of \"tree-based prediction, logic, unique prediction path and the complexity of decision rules\" (section 5.5), it seems to obfuscate the fact that oblique rules are harder to properly interprete than orthogonal rules or sparse oblique rules. As there is a consensus that depth in trees can be harmful, I would like to understand how the authors argue that for a relatively small depth (e.g. 5) and few features (e.g. 10) the resulting model is interpretable.\n\n**Minor comments**\n\n+ Just two typos\n\t+ (l 155): zero-viloation => zero-violation\n\t+ (l 156): positve => positive\n+ The term \"generate\" in Alg 1 (l12) is slightly unclear. Are the parameters $\\pmb{A}_{\\text{iter}}$ , etc, equal to $\\pmb{A}_{N_\\text{epoch}}$ , etc ?\n+ An anonymised repo link would have enhanced the review by ensuring that code was available.\n\nIf the authors convince me in addressing the few points above, especially regarding interpretability, I might raise my score.\n\n[1] Yang, Y., Morillo, I. G., & Hospedales, T. M. (2018). Deep neural decision trees. arXiv preprint arXiv:1806.06988.\n\n[2] Carreira-Perpinan, M. A., & Tavallali, P. (2018). Alternating Optimization of Decision Trees, with Application to Learning Sparse Oblique Trees. Advances in Neural Information Processing Systems, 31.", "was_revised": true, "final_justification": "I have decided to give a final score of 5 to this paper. The authors addressed my questions and concerns within the limit of what was reasonable and in scope with respect to their paper. The discussion brought up by other reviewers, and addressed by the authors were also interesting.\n\nThe paper is overall of good quality, and has sufficient material for complete reproducibility and understanding.", "rebuttal": "We sincerely thank the reviewer for the constructive feedbacks, as well as for recognizing the contributions of our work. Below, we provide point-by-point responses to address each concern raised.\n\n>**Q1-\"The discussion on the number of parameters in limited... the depth seems to be a user-defined parameter in oblique trees... Could the authors mitigate the cost of their accuracy improvements depending on the number of parameters?\"**\n\nThank you for the suggestion. We will include this parameter-based comparison in the revision to better clarify model complexity.\n\nTo clarify, tree depth is a key hyperparameter in all decision tree models, not specifically defined by our method. It determines the number of nodes, and thus governs the total number of parameters. While oblique trees require more parameters due to feature combinations, they can achieve similar accuracy with significantly smaller depth, meaning they do not necessarily require more parameters overall compared to axis-aligned tree CART.\n\nFor a D-depth tree with $T_B=2^D-1$ branch nodes and $T_L=2^D$ leaf nodes and a dataset with p features:\n- CART requires $T_B *2 + T_L$ parameters.\n- Our GET uses $T_B * p + 1 + T_L$ parameters.\n- Our GET-Linear uses $T_B * p + 1 + T_L * p + 1$ parameters.\n\nBased on results in Tables 1 and 3, CART achieves 74.85% accuracy with average depth 10.24 and ~3,141 parameters. GET and GET-Linear reach 82.39% and 84.63% accuracy at depths 7.29 and 4.82, using ~10,504 and ~4,045 parameters, respectively. Notably, if the goal is to match or slightly exceed CART's accuracy, our models can do so with much smaller trees. Our new comparison results show that GET achieves 75.23% at depth 2.82 using only 101.71 parameters, and GET-Linear reaches 77.21% at depth 1 with just 40.47 parameters, **yielding 31× and 78× reductions in parameter count compared to CART**.\n\nThus, **our methods do not necessarily require more parameters for improved accuracy**; the total parameter cost depends on the desired trade-off between accuracy and model complexity.\n\n|Method (Accuracy)|Depth|Number of Branch Nodes|Number of Leaf Nodes| Total Number of Parameters|\n|-|-|-|-|-|\n|CART (74.85)|10.24|1,046.65|1,047.65|3,140.94|\n|GET (82.39)|7.29|671.94|672.94|10,503.94|\n|GET-Linear (84.63)|4.82|129|130|4,044.71|\n|GET (75.23)|2.82|6.88|7.88|101.71|\n|GET-Linear (77.21)|1|1|2|40.47|\n\n>**Q2-\"a discussion on the training time specially depending on the number of samples, features, and tree depth would enhance the trade-off rationale.\"**\n\nThank you for your insightful comment. In Section 5.3 and Appendix K.8 and K.9, we provide a preliminary discussion, but we acknowledge this may not have been sufficiently clear. We clarify this here and will include it in the revision.\n\nSpecifically, our training time is primarily affected by three factors: the number of training samples $n$, features $p$, and tree depth $D$. For D-depth tree with $T_B=2^D-1$ branch nodes, each associated with an oblique split defined by $\\mathbf{a}_t \\in \\mathbb{R}^p$ and $b_t \\in \\mathbb{R}$. This results in a weight matrix $\\mathbf{A} \\in \\mathbb{R}^{(2^D-1) \\times p}$ and a threshold $\\mathbf{b} \\in \\mathbb{R}^{(2^D-1)}$. During training, each sample must be evaluated at all branch nodes via the matrix operation $\\mathbf{A}\\mathbf{x}_i$，requiring $O(p \\cdot (2^D-1))$ operations per sample and $O(n \\cdot p \\cdot (2^D-1))$ operations for the full dataset.\n\nThis trend is observed in our experiments. Table 4 shows training time increases with tree depth, while Table 5 demonstrates a similar increase with sample size in our million-scale scalability study.\n\nImportantly, our training pipeline is highly parallelizable and benefits significantly from GPU acceleration.\nThe advantages become more pronounced when dealing with larger matrix operations, especially for larger $n$, $p$ and $D$. Under ideal full GPU utilization, training can also be distributed across multiple GPUs, further reducing time in proportion to the number of GPUs used.\n\n>**Q3-\"Discussion on initialization could be improved... The binary classes are not specified for training SVM.\"**\n\nThank you for raising this important point. While we provided an example in Appendix E, Figure 3, we agree the explanation needs clarification and will revise it accordingly.\n\nImproper initialization, such as when $\\mathbf{a}_j^T \\mathbf{x}_i - b_j = 0 \\approx 0$, places samples close to the decision boundary. This can weaken softmin approximation, as near-zero and exact-zero violations produce similar outputs, reducing contrast in routing decisions (clear 0 for non-zero violation and 1 for exact-zero). To mitigate this, $\\mathbf{a}_j$ and $b_j$ should be initialized with sufficient margin to the boundary.\n\nEach branch test $\\mathbf{a}_t^T\\mathbf{x}_i \\leq b_t$ acts as a binary classifier, directing samples left or right. A practical adjustment is to slightly shift the decision boundary (e.g., by modifying the median of $\\mathbf{a}_j^T \\mathbf{x}_i$) to enlarge the margin without changing sample assignments. Beyond only adjusting $b_j$, we also refine both $\\mathbf{a}_j$ and $b_j$ using an SVM: **we treat left/right assignments as binary labels and fit a linear SVM to maximize margin**. The resulting weights and bias update the split parameters while preserving the original assignment. This procedure is visualized in Appendix E.\n\n\n>**Q4-\"Few missing references  e.g. [1] (Yang et al., 2018) [2] (Carreira-Perpinan and Tavallali, 2018) is absent from the discussion.\"**\n\nThank you for suggesting these two excellent studies. Regarding [2] of Tree Alternating Optimization (TAO) method, we have already included their regression tree with linear predictions (Zharmagambetov and Carreira-Perpinan, 2020), in our comparisons. \n\nAs for [1], the Deep Neural Decision Tree (DNDT) is indeed a pioneering work in gradient-based trees. DNDT reconstructs the tree as a neural network and relies on Kronecker products for class predictions. In contrast, our method offers an exact reformulation without altering its classic tree structure. While both are gradient-based, they differ in structure, formulation and optimization. We see them as complementary work suited to different applications and will clarify this distinction and include the DNDT reference in the manuscript.\n\n>**Q5-\"additional discussion on interpretability would be welcome... it seems to obfuscate the fact that oblique rules are harder to interprete than orthogonal rules. As there is a consensus that depth in trees can be harmful, I would like to understand how the authors argue that for a relatively small depth (e.g. 5) and few features (e.g. 10) the resulting model is interpretable.\"**\n\nThank you for your valuable feedback on interpretability. To address your concerns, we clarify our interpretability through both illustrative examples and experimental evidence.\n\nWe fully agree that **orthogonal trees like CART are more interpretable with a same depth**. However, as originally discussed in OC1 (Murthy et al., 1994), **oblique trees can be more interpretable when their required depth is significantly reduced**. For example, as shown in Figure 7, on a synthetic 2-feature dataset, our method achieves comparable accuracy with a depth-4 tree (16 rules), whereas CART requires depth-9 (512 rules). In such cases, the simpler structure outweighs the complexity of oblique splits.\n\nMoreover, as in our response to your Q1, our GET and GET-Linear achieve slightly better accuracy than CART while using smaller trees, average depths of 2.82 and 1.0 compared to CART's 10.24, **resulting in 30–70× fewer parameters**. For example, *a depth-1 tree consists of just two rules and remains highly interpretable*: \"IF the linear combination of features is below a threshold, THEN predict from the left leaf; OTHERWISE, predict from the right.\"\n\nRegarding your example of a depth-5 tree with 10 features, we agree that an orthogonal tree is easier to interpret at the same depth. However, our method typically achieves similar or better accuracy with far smaller depth, **reducing model parameters and rule count**.\n\n>**Q6-\"Minor Comments\"**\n\n>Q6-1 \"the term \"generate\" in Alg 1 is unclear. Are $\\mathbf{A}_{\\text{iter}}$ equal to $\\mathbf{A}_{N_\\text{epoch}}$?.\"\n\nThank you for careful review of our algorithm. We apologize for the confusion and would like to clarify it.\n\nThe term \"generate\" indicates that a tree candidate can be constructed based on the parameters obtained after $N_\\text{epoch}$ training. Specifically, $\\mathbf{A}_{\\text{iter}} = \\mathbf{A}_{N_\\text{epoch}}$ and $\\mathbf{b}_{\\text{iter}} = \\mathbf{b}_{N_\\text{epoch}}$, while $\\theta_{\\text{iter}}$ is derived through a deterministic recalculation and may not strictly equal $\\theta_{N_\\text{epoch}}$.\n\nAs described in Section 3.2, once $\\mathbf{A}_{N_\\text{epoch}}$ and $\\mathbf{b}_{N_\\text{epoch}}$ are obtained, the deterministic path of each sample can be computed, allowing us to identify sample-to-leaf assignments. For regression, $\\theta_t$ is recalculated as the average of the true targets $y_i$ assigned to that leaf.\nWe will revise the manuscript to clarify this explanation.\n\n>Q6-2 \"An anonymised repo link would have enhanced the review by ensuring that code was available.\"\n\nThank you for your interest in the code. We have indeed provided the complete code in a GitHub repository. The link is given in the last line of Page $2$ of the manuscript. We will also ensure it is publicly accessible upon acceptance."}, {"review_id": "QFpfXwYLMq", "reviewer": "Reviewer_Mko3", "summary": "The authors introduce a method to fit differentiable, oblique decision trees using ReLU+Argmin optimization. The method relies on a warm-start annealing scheme and a softmin approximation during optimization. The procedure can be sped up using GPU parallelization. Experiments against 14 tree-based baselines show performance improvements and speed-ups relative to optimal oblique trees for fairly large trees (up to depth 12) and fairly large datasets (e.g. 1 million samples). Overall the approach and results seem sound.", "questions": "- How does the inference time for the authors' proposed approach compare to the inference time for baseline models such as CART?\n- As the authors' method appears under-regularized, the authors may want to try [hierarchical shrinkage](https://arxiv.org/abs/2202.00858) on their trees", "limitations": "The interpretability of the proposed approach is not fully clear and the authors' discussion of it (Sec 5.4) does not seem to admit this. While RADDT can provide some interpretability, there is certainly a gap between RADDT and a concise axis-aligned decision tree (as suggested by Appendix A).", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "- S1: The author's problem is well motivated and the paper is well-written\n- S2: The authors' experiments are comprehensive and show strong improvements\n- S3: the authors' code appears fairly straightforward to use\n- W1: Much of the authors' speed-up comes from using relatively expensive GPU computation. Can the authors show how the method compares when using CPUs? Also, It would also be nice to see a quantitative comparison against baselines that are also amenable to GPU speed-up (e.g. a soft tree method, e.g. Hzeimeh et al. 2020 or Frosst & Hinton 2017).\n- W2: The authors are missing some discussion of related work, e.g. optimal axis-aligned trees such as [GOSDT](https://arxiv.org/abs/2006.08690).", "was_revised": true, "final_justification": "I think the authors for their clarifications and maintain my accept score of 5.", "rebuttal": "We sincerely thank the reviewer for recognizing the contributions of our work and for providing constructive feedback and insightful questions. Below, we address each of the comments in detail.\n\n>**Q1-\"Much of the authors' speed-up comes from using expensive GPU computation. Can the authors show how the method compares when using CPUs? Also, It would also be nice to see a quantitative comparison against baselines that are also amenable to GPU speed-up (e.g. a soft tree Hazimeh et al. 2020 or Frosst & Hinton 2017).\"**\n\nThank you for your thoughtful comment on GPU speedup. We would like to provide additional experiments and clarifications below. \n\nTo address the first part of your question, we conduct additional training time experiments for our method on both CPU and GPU. We use a fixed dataset with subsets varying sizes from {100, 1k, 5k, 10k, 50k} for training 8-depth and 12-depth trees. As expected, GPU training is significantly faster. For instance, on 50k samples with an 8-depth tree, GPU training is 117 times faster than CPU. For a 12-depth tree on 1k samples, we observe a 107× speed-up. On larger datasets and deeper trees, the CPU version often fails to complete within 5 days. This highlights the practical importance of GPU acceleration for scalability.\n\nAdditionally, as discussed in appendix K.8 and K.9 and also observed in this new comparison results, the advantages of GPU acceleration become increasingly pronounced with larger matrix operations, particularly involving deeper trees, larger datasets with more samples and feature dimensions. \n\n|  |8-depth tree|  |12-depth tree|  |\n|-|-|-|-|-|\n|Datasize|GPU (second)|CPU (second)|GPU (second)|CPU (second)|\n|100|337|615|769|10,912|\n|1,000|359|2,938|1,043|111,111|\n|5,000|466|22,082|2,799|OOT>5 days|\n|10,000|614|46,132|5,057|OOT>5 days|\n|50,000|2,949|345,992|41,564|OOT>5 days|\n\nRegarding your next question on GPU comparison with SoftDT (Frosst & Hinton, 2017) and TEL (Hazimeh et al., 2020), we would like to clarify that SoftDT already supports GPU acceleration in its original code. \nWe directly use their GitHub code without modification to ensure fairness. Their code utilizes GPU acceleration. As shown in Table 4, at smaller tree depths like 4, SoftDT is faster than our method. However, at larger depths like depth 12, our method achieves a 21× speedup compared to SoftDT.\n\nFor TEL, we also use their original code, which does not provide GPU acceleration but leverages C++ kernels for efficient forward and backward propagation.\n\nWe hope this clarifies the comparison and addresses your concerns.\n\n>**Q2-\"The authors are missing some discussion of related work, e.g. optimal axis-aligned trees such as GOSDT.\"**\n\nThank you for bringing this excellent work to our attention. GOSDT represents a key advancement in optimal sparse decision trees and complements earlier work on optimal axis-aligned trees without considering sparsity. We will cite it in the revised introduction to provide a more complete overview of optimal decision trees.\n\nRegarding experimental comparison, GOSDT may not be directly comparable to our method. First, it is limited to axis-aligned splits, which generally yield lower accuracy than oblique trees. Second, GOSDT is designed for binary features, requiring feature discretization that may degrade performance on our continuous-feature datasets. We therefore choose not to include GOSDT in our experiments, as it could unfairly disadvantage their method under our evaluation setting. We will clarify this rationale in the revised manuscript.\n\n>**Q3-\"How does the inference time for the authors' proposed approach compare to the inference time for baseline models such as CART?**\n\nThank you for your insightful comment on inference time, which greatly helps assess model complexity. **We compare the inference time of our method with CART from two perspectives**: **(a)** models with the reported accuracy in the manuscript (GET at 82.39%, GET-Linear at 84.63%, and CART at 74.85%); **(b)** models with similar accuracy (GET at 75.23%, GET-Linear at 77.21%, and CART at 74.85%). The second perspective is particularly relevant, as our models can match or exceed CART's accuracy while using much smaller trees. This enables us to explore more model variants by trading off a reduction in accuracy for significantly reduced inference time and model size. To ensure fairness, we average the inference time for each dataset over 10,000 repetitions and report the mean inference time across all datasets in the table below. \n\n- (a) As analyzed in our response to Reviewer oByt for Q1, CART achieves 74.85% accuracy with an average depth of 10.24 and approximately 3,141 parameters. In comparison, GET reaches 82.39% accuracy with a depth of 7.29 and ~10,504 parameters, while GET-Linear reaches 84.63% accuracy at depth 4.82 with ~4,045 parameters. In this setting, our methods involve more parameters than CART, and thus slightly higher inference time.\n\n- (b) However, if we aim to achieve accuracy comparable to CART (74.85%), our new comparison results show that the required depth of our trees can be significantly reduced, to 2.82 for GET and 1.0 for GET-Linear, resulting in only 101.71 and 40.47 total parameters on average, respectively. In this setting, GET still improves upon CART by 0.38%, while GET-Linear exceeds it by 2.36%. This yields a 31-fold and 78-fold parameter reduction compared to CART, respectively, with both models maintaining superior accuracy. **As a result, the inference time of GET becomes comparable to CART, while GET-Linear is even faster.** Note that all implementations use Python and PyTorch, where inference time may not scale strictly with parameter count due to framework overhead. In a pure C++ implementation, it would likely align more closely with parameter count.\n\n|Models with different accuracy|Tree Depth|Total Number of Parameters|Inference Time (second)|\n|-|-|-|-|\n|CART (74.85)|10.24|3,141|0.00044|\n|Our GET (82.39)|7.29|10,504|0.00188|\n|Our GET-Linear (84.63)|4.82|4,045|0.00161|\n|Our GET (75.23)|2.82|102|0.00054|\n|Our GET-Linear (77.21)|1|40|0.00039|\n\nIn summary, our methods does not necessarily require more parameters for improved accuracy compared to axis-aligned trees like CART. The total inference cost depends on the desired trade-off between accuracy and model size. Therefore, we utilized these two distinct perspectives (a) and (b) to offer a comprehensive comparison of the inference time between our method with CART. We will incorporate this clarification into the revised manuscript.\n\n>**Q4-\"As the authors' method appears under-regularized, the authors may want to try hierarchical shrinkage on their trees\"**\n\nThank you for suggesting this important study. Hierarchical shrinkage is an efficient post-hoc regularization technique for trees. We will cite this work in our revised manuscript as part of the regularization discussion and consider its integration in future research.\n\n>**Q5-\"The interpretability of the proposed approach is not fully clear and the authors' discussion of it (Sec 5.4) does not seem to admit this. While RADDT can provide some interpretability, there is certainly a gap between RADDT and a concise axis-aligned decision tree\"**\n\nThank you for your insightful comment. We are sorry for any confusion caused by the current discussion and will revise the manuscript to better clarify interpretability through both illustrative examples and empirical evidence.\n\nWe agree that axis-aligned trees like CART are more interpretable at the same depth. However, as originally discussed in OC1 (Murthy et al., 1994), oblique trees can become more interpretable when they require substantially less depth. For instance, on a synthetic 2-feature dataset (Appendix K.10, Fig. 7), our method produces a depth-4 oblique tree with 16 IF–THEN rules, whereas CART needs depth-9 and 512 rules, making our tree more interpretable despite the use of 2-feature combinations.\n\nAdditionally, as noted in the response to your Q3, our models can also achieve slightly better accuracy than CART with significantly smaller trees: average depths of 2.82 (GET) and 1 (GET-Linear), compared to 10.24 for CART, leading to 30–70 times fewer parameters. In this case, for example, 1-depth tree consists of only 2 leaf nodes with 2 rules, which is highly interpretable because we can explain the model predictions as \"IF the feature combination is less than a threshold, THEN the prediction is based on the left leaf nodes; otherwise, right leaf nodes.\" These experimental results highlight oblique tree's advantages in higher accuracy with smaller depth, typically yielding less prediction rules and fewer model parameters. \n\nTherefore, interpretability is not strictly tied to axis-aligned splits. It depends on multiple factors including tree depth, feature number, and the accuracy–simplicity trade-off, which may vary across different application scenarios. There is no interpretability superiority of one approach over the other, as it depends on the application context."}]

Author rebuttal:

Meta-review: The paper proposes an exact reformulation of hard-split oblique decision trees as an unconstrained objective built from ReLU terms and an argmin operator. Next it replaces argmin with a scaled softmin surrogate to enable end-to-end gradient training. A multi-run warm-start simulated-annealing schedule on the softmin scale is introduced to bridge the surrogate and true objective gap. Experiments across many datasets and depths (up to 12) show higher test accuracy than prior gradient-trained trees, and strong scalability with GPU parallelization. A link to the code is provided in the submitted pdf. Reviewers found the approach sound and empirically strong, with the method outperforming optimal/soft trees on large datasets. The authors perform ablations which show the usefulness of their proposed annealing schedule in achieving good local optima.

The ReLU+argmin reformulation (with a differentiable softmin surrogate) is viewed as original and well-motivated and the method is explained clearly. Broad and comprehensive comparisons are performed against tree baselines with variance testing. Solid accuracy gains and speedups are obtained on sizable problems. The results scale with depth, sample size, and GPU parallelism. The warm-start annealing schedule seems empirically effective. There are some concerns about insufficient hyperparameter optimization for strong baselines (e.g., XGBoost), and reliance on accuracy without additional more fine-grained metrics. Also, the authors should tone down the interpretability claims as they learn oblique trees instead of axis-aligned trees as suggested by multiple reviewers. Other than that the authors seem to give detailed and satisfactory responses to most points raised by the reviewers.

The paper is a clean, original and empirically overall strong contribution, and there is broad consensus for acceptance. Most issues may be addressed in a revision, but it is not clear if the gains will be as impressive (e.g. with more optimized baselines or across other metrics), so I am hesitant for nominating for an oral. Also while the paper seems to be clean, relatively thorough and likely impactful (reasons for spotlight nomination), I could see technical depth of contribution as a reason for bumping down to a poster.
Decision: Accept (spotlight)