A faster training algorithm for regression trees with linear leaves, and an analysis of its complexity
Authors: Kuat Gazizov
Miguel Á. Carreira-Perpiñán
Venue: NeurIPS 2025 poster ()
Keywords: regression trees
tree alternating optimization
Sherman-Morrison-Woodbury formula
Primary area: general_machine_learning

Abstract: We consider the Tree Alternating Optimization (TAO) algorithm to train regression trees with linear predictors in the leaves. Unlike the traditional, greedy recursive partitioning algorithms such as CART, TAO guarantees a monotonic decrease of the objective function and results in smaller trees of much better accuracy. We modify the TAO algorithm so that it produces exactly the same result but is much faster, particularly for high input dimensionality or deep trees. The idea is based on the fact that, at each iteration of TAO, each leaf receives only a subset of the training instances. Thus, the optimization of the leaf model can be done exactly but faster by using the Sherman-Morrison-Woodbury formula. This has the unexpected advantage that, once a tree exceeds a critical depth, then making it deeper makes it faster to train, even though the tree is larger and has more parameters. Indeed, this can make learning a nonlinear model (the tree) asymptotically faster than a regular linear regression model. We analyze the corresponding computational complexity and verify the speedups experimentally in various datasets. The argument can be applied to other types of trees, whenever the optimization of a node can be computed in superlinear time of the number of instances.

A Faster Training Algorithm for Regression Trees with Linear Leaves, and an Analysis of its Complexity
Kuat Gazizov
Miguel Á. Carreira-Perpinan Dept. of Computer Science and Engineering University of California, Merced
Dept. of Computer Science and Engineering University of California, Merced kgazizov@ucmerced. edu
pearteira-perrphaauuuuurrr edu
Abstract
We consider the Tree Alternating Optimization (TAO) algorithm to train regres- sion trees with linear predictors the leaves. Unlike the traditional, greedy recur- sive partitioning algorithms such as CART, TAO guarantees monotonic decrease of the objective function and results smaller trees of much better accuracy. We modify the TAO algorithm that it produces exactly the same result but is much faster, particularly for high input dimensionality or deep trees. The idea based the fact that, each iteration of TAO, each leaf receives only subset of the training instances. Thus, the optimization of the leaf model can he done exactly Woodbury formula. This has the unex- pected advantage that, once a tree exceeds critical depth, then making it deeper makes it faster train, even though the tree is larger and has more parameters. Indeed, this can make learning nonlinear model (the tree) asymptotically faster than regular linear regression model. We analyze the corresponding computa- tional complexity and verify the speedups experimentally in various datasets. The argument can be applied other types of trees, whenever the optimization of a node can be computed in superlinear time of the number of instances.
but faster by using the Cherman-Morrisone Morrison-Woodbure
1 Introduction
Decision trees have been a popular model in machine learning and statistics for many decades, having high interpretability and fast inference as major advantages, as well as very high accuracy when ensembled in forests. We consider trees making hard decision at each node (rather than soft decision trees). We consider regression (rather than classification) trees, which define mapping from R to E (where E = is scalar regression), and we focus on oblique trees with linear leaves. Oblique trees use (possibly sparse) hyperplane split at each decision node and are much more powerful than axis-aligned trees (which use fingle-feature split) while remaining interpretable. (That said, all the results in this paper carry over to the axis-aligned case as well.) Linear leaves, which use linear mapping A,x + b, as predictor, work much better for regression (i.e., continuous outputs) than constant leaves, which predict a constant output vector.
The traditional algorithms to learn regression trees, such as CART (3] or C5.0 and M5 [19 20 are based on greedy recursive partitioning and have been used for decades. While they are fast, simple and intuitive, they do not optimize global objective function of all the parameters in the tree, so they produce overly large trees and achieve low accuracy, particularly for oblique trees and/or for linear leaves. We focus instead on the family of Tree Alternating Optimization (TAO) algorithms, proposed more recently for classification (5), regression (28) and other tasks. TAO provides proper optimization of well-defined objective function, so that each iteration decreases the error leaves constant. Compared to CART or M5, this produces trees that are much smaller and much more accurate. The key idea of TAO, explained in detail for regression in section 3 is to optimize the
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

parameters of one node at a time in the tree, typically depthwise from bottom to top. One pass over all the nodes constitutes one TAO iteration. which is then repeated until convergence. This has important consequences: within each iteration, all nodes at the same depth can be optimized in parallel (separability condition); and the optimization of a single node (reduced problem) takes the form of a weight 0/1 loss binary classifier over decision node, and of a linear regression fit over a leaf. The latter requires the solution of a linear system with a coefficient matrix of D x D, where D is the input dimensionality.
It turns out that this algorithm can be substantially accelerated while producing the same exact result. We give here an overview of the idea and full details in sections 3 and 4 We focus on the step over the leaves" TAO has the peculiarity, unusual compared to most machine learning algorithms, that it never optimizes a model (here, leaf predictor) over the whole dataset of size N instances. Instead, since the decision nodes make hard decisions and so the leaves partition the whole dataset into disjoint subsets, TAO fits independently a separate predictor (A,, b&j for each leaf over only the instances currently reaching that leaf (its reduced ser). Thus, the deeper the tree, the smaller the reduced set at each leaf; and, if the tree exceeds a critical depth A = loga T and is complete (i.e., having 2 leaves for a depth A) and balanced (i.e., having uniform reduced sets, each with M- = N2 A instances), then each leaf receives fewer instances than the number of features (dimensionality D). This makes the D x M data matrix X have rank at most M (rather than D. as would typically be in practice). Thus, we can use the Sherman- Morrunso-------- Woodbury formula [13 section 0.7.4] to solve the linear system exactly but inverting an M x M matrix (involving X X) rather than- as done in the original algorithm inverring D x D matrix (involving XX"). This results in a considerable speedup, particularly for high input dimensionality or deep trees.
N
The underlying principle here is that, if we have a problem whose cost on the sample size is No for E IR, then partitioning the N samples equally into B disjoint groups and solving them has a total cost B'B'' i... Bi~a times the cost without partitioning. If a this cost is independent of B, as happens with oblique decision nodes. But a > (superlinear cost), as happens with leaves with linear predictors, then solving for the partition is Ba-1 times faster. For the commonly occurring quadratic (a = 2) or cubic (a = 3) costs (as with solving linear systems) and when B is large (note B = 2 for complete binary tree), the speedup can be huge.
This means the cost of the leaf step in our algorithm not monotonically increasing with the depth (hence model size): it first increases until the critical depth A", then decreases. This has the unex- pected advantage that, once tree exceeds the critical depth, then making the tree deeper makes the leaf step faster to train, even though the tree is larger and has more parameters. Indeed, for deep enough trees and considering the total cost (decision nodes and leaves). this can make learning a nonlinear model (the tree) asymptotically faster than learning regular linear regression model.
The above discussion assumes sequential updating of the nodes. However, in TAO all the nodes at the same depth define independent optimization problems, so they can be trained in parallel. Combined with the adaptive computation above, this makes the computational complexity much faster still.
What if the optimal tree size for a given dataset is not deep enough? In practice, fitting model involves cross-validating its hyperparameters, usually by a grid search, which requires training trees of multiple depths. Thus, even if the final model selected is shallower than the critical depth (which may or may not be depending on the case), we do need to train deeper trees during the grid search, where our improved algorithm will speed up the training.
In summary, our paper has the following contributions. First, we propose an exact but faster Icaf step, which makes our algorithm always better than the original one of (28). This is described in section 3.J after we review in detail the original algorithm in section Second, in section we ana- lyze the computational complexity of our algorithm and show how the leaf step has non-monotonic runtime across the depth domain (from depth O, corresponding to a regular linear regression, through the critical depth, to depth log, N. where each leaf has single instance). We also point out that the idea applies to other types of trees, having decision nodes or leaves with superlinear cost on the sample size. Finally, in section 5 we verify the speedups experimentally (in the sequential compu-
'The idea applies to the decision nodes as well, but it makes no difference if decision nodes have a computational cost @(N D) that is linear on the sample size, as is the case for oblique or axis-aligned trees, which we focus on here. However, if using decision nodes with a superlinear training cost on N, such as a kernel machine, the same mon-monotonic cost would occur.

---

tation setting only) in various real-world datasets, where the reduced sets need not be balanced. We compare the original ("naive") algorithm of (28). which optimizes each leaf by solving a D D linear system in the regular way (cubic cost on D); and our "adaptive" algorithm, which chooses the regular way or the SMW one depending on the leaf depth. We also apply the SMW formula to a traditional tree induction algorithm (CART) and show even larger speedups- as expected, since the trees it learns are much deeper than TAO's.
2 Related work
The literature on decision trees is vast. Here we focus on work on regression trees having lin-
predictors in the leaves. Decision trees date back to the 1950s 12 21. 25I, and typically use axis-aligned splits B. 20 or oblique and sparse oblique splits B. Sl. with constant models at the leaves. Trees with linear leaves were first introduced in the M5 "model tree" [19] (further studied in [24, 25)), where a linear regressor is fit at each leaf after constructing a tree with constant labels using greedy recursive partitioning. The constant labels at the leaves are then replaced with linear models trained on the data reaching each leaf. Several variants of this idea have been proposed, including modifications to the splitting or pruning criteria (27. 177. However, these methods remain fundamentally suboptimal for two main reasons: 1) the tree is constructed greedily by optimizing an impurity measure such as variance, and 2) the structure learned under the assumption of constant outputs, ignoring the actual form of the final linear leaf models. As a result, the induced trees tend to be unnecessarily large and prone to overfitting [17. More recently, exact optimization methods have been proposed using dynamic programming to construct globally optimal piecewise- lineer regres- sion trees [22]. While theoretically appealing, these methods do not scale to high-dimensional inputs or deep trees due to their combinatorial nature, and they rely on discretizing the input space via fea- ture binarization. As such, they effectively solve a different problem from the original continuous formulation and are limited in practical applicability.
Optimizing decision trees difficult because 1) the tree makes a hard decision at each node, which makes it a non-differentiable function, and gradient-based methods do not apply; and 2) there is a huge number of tree structures. Indeed, even in its simplest version (axis- aligne splits and binary inputs and outputs), the problem of training a decision tree is hard [14]. The traditional greedy recursive partitioning procedure, such as CART [3] or C5.0 (20), is an approximate way to solve this problem, but it does not optimize an objective function of the entire tree's parameters (involving well-defined loss function and regularization term, as with most modern machine learning models). This results in suboptimal and overly large trees. The Tree Alternating Optimization (TAO) algo- rithm (5) does optimize such an objective function and is scalable to large datasets. It assumes a given tree structure with parameters at the nodes and then optimizes the objective function over one node at a time in alternation, decreasing it at each step until convergence to a local optimum. The tree structure (e.g. its depth) can be selected by cross-validation. TAO produces trees that are both more accurate and smaller than greedy recursive partitioning [30]. The fact that TAO can optimize an essentially arbitrary choice of loss function and tree model has also made it possible to develop it for tasks to which trees have rarely been applied before, such as clustering [9. dimensionality reduction [4] semisupervised learning [29]. well to optimizing forests 6. In this paper, we focus on the case of trees with linear leaves (28).
3 The original TAO algorithm for linear leaves and our speedup
The basic optimization algorithm for trees with linear leaves we use is the one in 288] We give a self-contained description here. Our version is more general, allowing for a quadratic penalty on the linear regression weights (i.e., ridge regression). Later, in section 3.1 we describe how we modify it to speed it up.
Consider a fixed rooted directed tree structure consisting of decision nodes and leaf nodes, indexed by sets D and f., respectively. The full set of nodes is N D U f. Each decision node routes an input instance x E RDD based on a decision function f 0.): RD + C, = (left, right,]. The
In fact. the idea for the present work came from the tree autoencoder model [4]. which first reported a non- mom-moootonic cost for the leaf step as function of the tree depth. There, each leaf of the tree contains linear autoencoder (PCA), i.c., a low-rank linear regression.
3

---

decision function determines whether an instance is sent to the left or right child of decision node For oblique decision trees, if w/ x + w/o 2 O. the instance x is routed to the right child (i.e., (x; 0:) = ri rightt), and to the left otherwise, where 0: = (Wi, W00 ). Leaf nodes predict outputs for instances within their decision region by applying g: (x:0,): RD + RE In our case, we define linear mapping gi (x; 0,) = A; + b,, where O. {A, bi A, E REXD and b, E R Finally, we define tree mapping T(x; )): R - RR where @ = (0, i E LUD) The tree routes an input instance x along a unique path from the root leaf, where the corresponding leaf predictor is applied to produce the output.
To optimize the tree parameters, we define the following objective function for given training set yyll is the squared 2--norm loss:
(n)) CR x H,, where y(y, = -
E(O) = Σ Lyy T(x;; θ))
Σ iED
|wlll + ΣIAMI
(1)
jEC
(throughout, all norms are Frohenius norms unless otherwise indicated). The regularization parame- ters À 2 0 and a > 0 control the ε penalty for decision node parameters w, and the l2 penalty for leaf node parameters A, respectively. We also define the reduced set R2 C {l...., N of a node i E N as the set of training instances that reach i given the current tree parameters.
The algorithm is based on three key theorems, which we briefly discuss below. Detailed proofs can be found in [5]. We assume that the objective function E(O) is separable over training points and that parameters 0, are not shared across nodes.
Theorem 3.1 (Separability condition). Let T(x: θ) be the regression tree mapping, and i.j E N be two nodes that are not descendants of each other. Denote the parameters in node i and j by O: and 0,. respectively. Let all other node parameters O rest O (0:,00 be fixed. Then the function
F ()) of eq. ① can be equivalently rewritten as
E = (O.,,, O ress) + E2 ress) + Erest rest)
(2)
where Ej does not depend on 0,. Ej does not depend on O,, and Erest is independent of 0; and 0z-
The main idea of this separability condition is that the reduced sets and weights of non descendant nodes are disjoint. As a result, each pair of non descendant nodes can optimize parameters indepen- dently using only their respective reduced sets.
Theorem 3.2 (Reduced problem over a decision node). Consider the functiovefunctoon E(O) from eq. ① and a decision node i E DD. Assuming that all other node parameters remain fixed, the optimization problem minw,,wo wio E(O) can be reformulated in the following way:
min WL,200
Σ
Tisn (Teee Ji(Xn; Wi, WHo)) + +|[[wall,
(3)
nER:
where: R; is the reduced set of node i; define the weighted 0/1 loss Lin (Tm: )): Ci
RR U U{}} for instance Xn. E R4 as Lin (T::: = Lin(y) - lon (Ta) Vy E C, where lin(2) llyn (x, Oz) and [= 2.) is the predictive function for the subtree rooted at node and we define the pseudolabel Usn as the child of i that routes X,, to the the leaf with the lowest squared lz-norm loss (in the case of tie, where the losses for both children are equal for an instance X., the instance Xn, can be removed from the reduced problem, as its routing does not affect the loss).
The pseudolabel Un represents the preferred child for instance x,,, determined by comparing the two losses incurred when routing it to the left and right child nodes and selecting the child with smaller loss. The weight assigned to X,, is the absolute difference between these losses, defined as Yin [l..f.tt.)) - Iin (right;)). ) Thus, this results in a weighted 0/ 0/1-loss binary classification problem. Since optimizing this is NP- we obtain an approximate solution by instead minimizing an lrrregularized surrogate loss (we use logistic regression).
Theorem 3.3 (Reduced problem over a leaf node). Consider the objective function E(() of eq. and a leaf node i E L. Assuming that all other node parameters remain fixed, the optimization problem minA.b b. E(O) can be reformulated in the following way:
min Σ Ily (A,x, + +b,)1l Al1.. A.,b, nER,
(4)
4

---

The solution to this ridge regression problem is given by the following closed-form expression:
A = CK-
by - y, A,Xi,
where x; = [R E..EEER X y, = R. EMER, Nu. C= EmER, (yn F.)(xn - -x.) is the cross-
covariance matrix and K = ENER. (Xn. - {x) -x,"" all is the regularized covariance matrix of the input, with regularization parameter (Ip is the identity matrix of size D).
The algorithm pseudocode is presented in the appendix. Despite the algorithm''s 's complexity, it can be summarized an iterative algorithm that optimizes tree nodes in depthwise fashion until con- vergence. Each node is trained on its corresponding reduced set. Decision nodes learn to route training instances to the leaves where they achieve the lowest error, while leaves are trained stan- dard regression models. Each node update decreases the objective function or leaves it unchanged (if the approximate solution from the surrogate loss increases the objective, we skip the update). The hyperparameter can make ||will = for a decision node i, effectively pruning one of its children, which results in TAO learning the tree structure (subject being contained in the initial tree).
3.1 Fast solution of the leaf step using the SMW formula
Since the training set partitioned over the tree leaves, each Ieaf receives only subset of the training instances. If subset size is smaller than the input dimension, we can solve its leaf linear system exactly but much faster using the therman--orrison Woodburyy (SMW) formula [13 section 0.7.4) This states that if H E IR U E R V E R"x", and J E IR" are given matrices such that H. and J VH U are nonsingular, then the inverse of H + UJV can be computed as
(H UJV) H H HU VH VH 'U) VH
In case, assuming both matrices data X. Y are centered, involving the regularized covariance matrix Xx" + +aIp of D x D, which has a computational cost of O(D*). However, using the SMW formula (substituting H = alp, U X. J IN. V V
need to solve linear system
we obtain an expression based on the regularized Gram matrix of x N:
(XX* + alp) = - a- x (aIN X XT.
This formulation implies that instead of solving a linear system of size D D, we can solve an N x N system. We select the method with the lower computational cost based on the relative sizes of N and D by applying the following formula at each leaf (where X represents its reduced set):
(Xx + +
D DSN N N
k-t
a (ID - X (aIN + X -T)),
< D.
The leaf weight is given by = CK- (Computationally. we do not compute a matrix inverse explicitly, but solve its associated linear system, which is faster and more stable.) This works not just for TAO but also for the traditional greedy recursive partitioning algorithms CART and M5.
Analysis of the computational complexity
We now give the computational complexity of our accelerated TAO training algorithm for oblique decision tree with linear leaves. The formulas are somewhat involved because the computations depend the size of the leaves' reduced sets. Consider complete binary decision tree of depth with sparse oblique decision nodes. We assume a sparsity coefficient s E [o, 1). where s = 0 corresponds to completely sparse weight vector w, and = 1 corresponds to a fully dense weight vectoff. Let the total number of training instances be N, the feature dimension be D, and the output dimension be E. We assume that the training instances distribute uniformly over the leaves ("balanced case"), so each leaf contains M = N/2² instances; this is the best-case runtime. The worst-case corresponds all instances going to the same leaf. In our experiments we observe wide variation in leaf reduced set sizes, depending on the dataset. We apply the algorithm in bottom-up fashion: leaves are trained first, followed by their parent nodes, up to the root. Below, we provide time complexity analysis for one iteration of this process for decision and leaf nodes.
Although s varies across decision nodes and during training (as some weights become zero or nonzero), we take it to mean the average proportion of nonzero weights across nodes and across TAO iterations. This is valid because appears linearly in the runtime formulas.
5

---

4.1 Leaf nodes
The separability condition in TAO allows all leaves to be optimized independently, they are non- descendant to one another. Training each leaf requires solving a ridge regression problem, which has a computational cost of (M D D) This cost accounts for computing K and solving the linear system. Since K is positive definite, we apply the Cholesky decomposition, with cost of /3/3 flops 11. Section 4. The total cost for 2 leaves therefore O D2 D F)F) = O(ND2 + 2 D3 D2 )) The exponential dependency on the tree depth A appears impractical, but using simple linear algebra techniques, such as the Therman-Morrisee Woodbury formula, can significantly reduce this complexity. Call A / D) the critical depth.
We define two regimes for training each leaf based on the relationship between M N/22 and D: deep regime, if M < D, which occurs when A 2 A and shallow regime, when A < A'. The final cost for training all leaves
Cost O (ND2 D D min F2 NDE). (N2 + N min B)+ N NDE), A >> A
A S A'
(N2
These formulas, while correct, appear complicated to understand and also give the misleading im- pression of having large costs, because of the terms on 2 D N etc. However, by applying the inequality in each case (A S A' or A A*) it follows that the runtime in both regimes is upper bounded by O D2 + NDE). Importantly, this shows that, across the whole range of depths from 0 to logg N:
We do not incur a large, cubic cost @()²) or @DD²)) (repeated for each leaf, i.e., 2 times) by naively solving a linear system for the linear mapping matrix A; of E x D. The cost is only proportional to D(D + E), i.e., quadratic on the dimension.
We do not incur a large, cubic cost on N. The cost is only linear on N.
Two extreme cases arise when: 1) a leaf contains one instance (i.e., A = loga (N)), which has complexity O D + NE + N DE);
; 2) the tree has depth zero, so the tree reduces to a single ridge regression model with complexity O(ND* D2 + NNDE D DD Thus, deep enough tree (which a nonlinear regression model) has a lower asymptotic complexity than a regular linear regression.
In summary, what we have here is happy collusion of two factors. First, a cost for the leaf predictors that depends either superlinearly on the dimension D (and E) and linearly on the sample size N. or vice versa, depending on how it is computed: solving the regular linear system or using the SMW formula. And second, an effective sample size -2-A A each leaf that decreases (exponentially) with the tree depth. Thus, switching to the computation that is superlinear on N (the SMW formula) when the tree deep enough (i.e., when each leaf receives fewer instances than dimensions) makes the total cost over all the leaves faster-so so much so that the cost even decreases with the depth.
As shown above, in the deep regime the SMW formula is always faster, but how much? This can be seen by comparing the shallow and deep regimes' costs: the speedup is faster the deeper the tree is, or the larger the dimensionality D is (and thus the lower the critical depth is).
The particular case of scalar regression (E = 1) A common case of regression is when we predict a scalar value rather than a vector. In that case, the complexity simplifies as follows:
T@ND2 + D324 + ND), L0(N222-420 N 22 + ND),
A < A
Cost
A > A
For deep enough trees, the term NN DE becomes N D, so the algorithm has no quadratic complexity on the dimension anymore, while the regular linear regression still contains terms that are quadratic and cubic on the dimension.
4.2 Decision nodes
Decision nodes are trained level by level. For single decision node, the training process involves two steps: first, constructing reduced problem by sending each training instance to both child nodes and computing their respective losses. Second, solving the constructed reduced problem with a logistic regression. To derive the total cost of all decision nodes, note that at the same level, the

---

total number of training instances equals N,, and the tree has A levels of decision nodes. Then, the cost for constructing reduced problems for all decision nodes is: e ( SNNDA 1) NDEA). For solving the logistic regression problems, assume that each solver requires iterations on aver- age. The total cost of solving logistic regressions across all levels is (cNDA) Thus, the total computational complexity for training decision nodes is @(NDA² + (D +)
4.3 Overall complexity
Combining the costs for leaf and decision node training, the total cost per iteration is O(NDA² N + NDE + N (DE + c) Thus, the overall cost is linear on the number of instances N and quadratic on the dimensionality D or E. Note that this is asymptotically faster than solving single ridge regression, in spite of the increased complexity of the tree's training procedure.
Training parallelization At level I {O...., A}. each node contains N/2' training instances. Given 2 cores, we can process all nodes at each level in parallel. Consequently, constructing reduced problem can be distributed across training instances, resulting in 2 speedup. The training complexity of all logistic regressions in the decision nodes is upper-bounded by a geometric series, resulting in O(2N DA), which has A/2 speedup over the sequential computation. For leaf training, each core is assigned exactly one leaf, reducing the training time by a factor of 2 over the sequential computation.
Inference time Inference refers to mapping an input instance x E RD to its corresponding leaf and applying a leaf predictor compute the output. This involves traversing single root-to-leaf path of depth A. Given that the decision nodes are sparse, the cost of this traversal is ((sDA), where is the sparsity coefficient of the decision nodes. Once the input instance reaches leaf j. the leaf predictor computes the output as A,x + by, which has a cost of (ED)). Thus, the total inference cost is (D(ss + F.))-
Model selection In practice when training a model on real data, the final tree (with best generaliza- tion) may be shallow or deep, depending the case. This will be determined by model selection criterion, such as cross- validation, over the depth and other hyperparameters of the tree, which typ- ically requires grid search. Whether the grid search is directly over A over the decision node sparsity hyperparameter X, this will result in leaves whose depth spans a range of values both below and above the critical depth A The speedup of our algorithm will occur in the depths above A
One problem with very deep trees is that the number of leaves and hence of parameters (in the linear mappings) becomes very large (particularly if the output dimension E' is high). Also, the resulting tree would likely overfit. This can be solved by using low-rank linear mappings, which are particularly suitable if there are fewer samples than features. This is a new type of tree model that we are working on and will report elsewhere
Experiments
We evaluate the speedup of our algorithm ("adaptive") over the original algorithm ("naive") of [28] in several settings and verify that the models and RMSE obtained are the same for both (up to small numerical differences). We focus speeding up TAO and some experiments also do this for
CART linear trees (although they have a far lower accuracy, as shown in (28)). We implement the algorithm in C++ using the Eigen library [11] for linear algebra operations and LIBLINEAR [7] for solving & Er-regularied logistic regressions. The oblique decision tree is randomly initialized: each scalar weight is sampled from standard normal distribution, and biases adjusted to ensure that training instances are uniformly distributed across all leaves. Although TAO is highly parallelizable, we do not conduct experiments with parallel computation (section gives brief discussion). For preprocessing, we use the Python library PIL. with a bilinear resampling filter for resizing and the nd ndimage package for rotation. For the Infinite MNIST dataset [18], we generated IM points.
5.1 Speedup function of sample size, depth and feature dimension
Fig. 1 compares the naive and adaptive TAO versions with an oblique decision tree with linear leaves trained on the MNIST dataset (N 60 000). We fix the regularization parameters to À 1 and

---

Leaves
Decision nodes
Overall
Leaves
80-
10
600
Naive
400
40
600
10"
400-
10
200
200
10
15
0
10
15
0
10
15
10
10"
10"
109
+0=10x10
60
10
Adaptive
1-D=20x00
A
D=28x28
10"
4
17-00000
+
10
10 Depth A
15 0
10 Depth A
15 0
Depth X
15
100
10 10t 199
#
samples N
Figure 1: Training time (in seconds) for a single iteration on the MNIST dataset (D = 784) using the adaptive (top row) and naive (bottom row) algorithms for leaf training across different input dimensions and depths A. Columns 1-3 show the training time for leaves, decision nodes and its total sum, respectively,
function of A. Critical depths A indicated by black dots each curve. Column shows leaf training time as a function of the sample size N. Black dots now mark the critical sample size N* corresponding to each depth. Sample sizes smaller than or equal the N correspond to the deep regime, where the speedup occurs. Error bars indicate standard deviation over runs.
Naive
Adaptive
Figure 2: Training time (averaged over runs) of all leaves for a single iteration on the MNIST dataset (D 784) us- ing the adaptive (left column) and naive (right column) algorithms for leaf train- ing across different output dimensions E and depths A.
Training time, $
50
50
A =
les
25
A 12
100
400
900
1600
100
400
900
1600
output dimension
output dimension E
0.001, and construct curve of training time over tree depth A for different input dimensions D. To generate datasets of different dimensions, we resize the MNIST images from their original size of 28 28 to 10 10, 20 x 20 and 40 x 40, resulting in 4 datasets with feature dimensions D = {784, 100, 400, 1600} and corresponding critical depth A = (N//(N z {6, 9, 7) respectively. Single-output regression labels generated by applying random projection unique to each class. Note that training at depth zero corresponds to solving a single ridge regression.
Starting from depth A = 10, which corresponds to the deep regime for all datasets, training all leaves with the adaptive algorithm takes less than a second. For D = 1600, training all leaves at depth 10 is 8x faster than training single ridge regression model, and 16x faster at depth 15. The training cost for all leaves has a non-monotonic behavior, decreasing after the critical depth. contrast, the naive algorithm results in exponential time complexity with respect to A. This behavior is shown in fig. ① (row 2), where leaf training dominates the overall training cost for deep trees, leading to an exponential total training time. Decision nodes, on the other hand, have similar training times for both the naive and adaptive algorithms, as they are unaffected by the specific leaf solver, and the time is linear over N.
In order to use larger datasets, we used IM images of 28 x 28 from the Infinite MNIST dataset images; the input dimension D = 784 and output dimension E 1 are fixed. Fig. DI (column 4) demonstrates that the training time scales linearly with the number of samples for both the naive and the adaptive algorithms. The black dots mark the critical sample size N for the given tree depth A and input dimension, i.e., N = D2 As A increases, N shifts to higher sample sizes, showing how the boundary between the deep and shallow regimes changes with depth. The training time curve lies in the deep regime for < N and in the shallow regime otherwise.
Fig. 2 shows the effect on the training time of the output dimension E. For both the naive and adaptive algorithms, the training time scales linearly with E because both the leaf and decision node computations are linear in F. The critical depth here is A = 6, so the red curve represents the deep

---

regime and the blue curve the shallow regime. Although both algorithms scale linearly with E, the naive one has larger scaling factor of ( )²). while for the adaptive one is only ((ND). This indicates that while both methods experience increased training time as E grows, the adaptive approach remains significantly more efficient in deep regimes.
5.2 Speedups on various real-world and synthetic datasets
Tsoos the training time of oblique decision trees other datasets (whose descriptions are in the appendix), across shallow and deep regimes, using the naive and adaptive algorithms. All trees are trained with fixed hyperparameter values a = 0.01 and À = 1 for 20 iterations. The RMSE value (not shown) is identical for both algorithms. We present results ranging from small to large scale. The difference in training times becomes more pronounced for datasets with higher imput dimension and larger sample size. For example, on moderate-sizze sized datasets such as CT Slice, Rotated MNIST and Patched Fashion MNIST, the adaptive algorithm achieves up to 3.5x speedup over the naive one. On the datasets with high input dimension (e.g. D 500), the speedup reaches 25x.
Our complexity analysis in section assumed a best case: complete trees (with 2 leaves for depth A) with balanced leaves (having the same number of instances N/2 However, our experiments are not restricted in that way. For example, in the TAO and CART linear trees of table the number of leaves is much smaller than 2 indicating an irregular structure, and the reduced set sizes range from 8 to 5649 instances. Still, the adaptive algorithm shows significant speedup.
5.3 Speedup on regression forests using bagging
Table I: Training time (s) averaged over 5 runs for 20 iterations at different tree depths A: adaptive vs naive algorithms.
The accuracy can be considerably increased if using an ensemble of trees (forest) rather than single tree. Here we demonstrate this using bagging as ensembling mech- anism, in (28). This means we use T oblique trees, each trained independently on a bootstrap sample (or strict subset, by subsampling) of the original dataset, and define the forest output as the average of the T trees. Our adaptive algorithm applies to each single tree, so the run- time gains (relative to the naive algorithm) are the same as if using single tree. However, if using subsampling in bagging, each tree is trained on a subset having fewer than N samples, so the critical depth becomes smaller, and the algorithm becomes faster.
Dataset
D Impl. A
T
Time (s)
adap. naive
7.67
ailerons 40
13
7.66
adap.
119.12
CT slice
384
naive
15
243.25
adap.
34.72
sarcos
naive
16
34.85
adap.
1160.24
Patched
784
naive
15
3990.65
adap.
6611.74
Rotated
784
15
17534.83
adap.
3273.18
Random
2500
naive
15
83387.20
adap.
89.47
Table I shows results for the Patched Fashion MNIST dataset using a forest of size T = 30 trees with depths ranging from to 15. Each tree is trained for 20 itera- tions with a strict sample size of 90% of the training set.
Patched
784
naive
3
30
89.06
adap.
217.58
Patched
784
naive
222.54
adap.
331.66
Patched
784
naive
11 30
515.36
adap.
580.12
Patched
784
naive
15 30
1995.32
5.4 Speedups across hyperparameter tuning
We evaluate the speedup in the practical setting of model selection by cross-validation, where get the final model one needs to train multiple trees spanning a range of hyperparameter values and pick the best one. Since the adaptive algorithm does not change the learned trees, hyperparameter tuning and model selection is as with the naive one. We consider two methods of hyperparameter tuning.
Grid-search hy hyperparameter optimization We use grid search over the regularization parame- ters X and a but not over the depth, which we set to relatively large (e.g. A = 15). This is because varying A will automatically reduce the number of nodes from the initial, complete tree and produce a regularization path of trees of different number of leaves, each having possibly different depth, and thus an irregular, learned tree structure. Thus, this grid search necessarily evaluates many trees of both deep and shallow regimes. In fact, when training trees of irregular structure, the idea of deep/shallow regime really applies to each individual leaf, which has its own depth. It is possible that the final selected model is shallow (i.e., A < A') and thus would not, for its final training, benefit from the adaptive speedup. However, this outcome cannot be known in advance. To find the optimal model, the grid search must evaluate the deeper trees (i.e., those with A > A*), as the best

---

Table 2: Left: grid search time and final model training time on the Patched Fashion MNIST dataset. A denotes the depth of the final selected model, chosen from a regularization path that started at depth 15 for TAO and from fully-grow tree for CART. Right: counts of sampled tree depths for Bayesian hyperparameter optimization frameworks Optuna and Hyperopt (100 trials each).
Grid search
Bayesian hyperparameter
Train RMSE
Test RMSE
Search time, 8
Training time,
Model
A
optimization
Depth range
Optuna
Hyperopt
TAO-lin, adap.
10
0.11
0.16
3485.38
253.82
TAO-lin. naive
10
0.11
0.16
6899.90
256.05
1-10
4
CART-lia. adap.
0.09
0.19
350.37
45.79
11-20
17
5
CART-lin. naive
0.09
0.19
2444.19
54.08
21-30
64
62
Random Forest
47
0.06
0.18
N/A
2734.23
31-40
15
29
XGBoost
0.11
0.17
N/A
2117.93
model may be in that regime. Our adaptive method provides a significant practical advantage by ac- celerating the evaluation of these deeper trees. Therefore, the total computational cost of the entire hyperparameter search is significantly reduced, as shown table 2 (left). Note how the speedup for CART is much larger than for TAO; this is due the fact that CART trees much deeper and larger, in turn due to the suboptimality of CART as tree learning method.
Bayesian hyperparameter optimization A reviewer of this paper conjectured that using more sophisticated hyperparameter optimization (HPO) method instead of grid search, such as Bayesian hyperparameter tuning, might sample deep trees often if they overfit, which might reduce the speedups achieved. To test this, we use Bayesian hyperparameter tuning for CART with linear leaves on the Patched Fashion MNIST dataset, using two HPO frameworks: Optuna [1] and Hyperopt [2]. Following standard practice for CART (12), we tune the cost-complexity pruning parameter. We run each framework for 100 trials with a time limit of hours, minimizing the RMSE loss. The results in table (left) demonstrate that our adaptive method is critical for the feasibility of these advanced HPO frameworks. The adaptive algorithm completed the full 100-trial search in under an hour. In contrast, the naive algorithm timed out after hours, completing only 28% of the scheduled trials.
Furthermore, we analyze the distribution of the tree depths sampled by these frameworks address the hypothesis that they would avoid deep trees. The results, shown in table 2 (right), demonstrate the opposite is true. Using Optuna, 79 of 100 trials resulted in trees with depth greater than 20. The trend was even more pronounced with Hyperopt, where 91 of 100 trials resulted in trees with depths greater than 20.
This provides strong empirical evidence that Bayesian HPO frameworks not avoid deep trees; on the contrary, they must extensively explore complex, deep structures to find the optimal model. This finding underscores that our adaptive speedup is not just beneficial for grid search, but in fact essential for making modern HPO techniques computationally feasible.
6 Conclusion
We have improved the TAO algorithm for trees with linear leaves by making it considerably faster while producing the exact same result. We have achieved this by noting that the optimization over the leaf predictors separates over disjoint subsets of the training instances. The corresponding linear system can be solved either in the usual way, with cost cubic on the input feature dimension, via the Sherman-Morrison. Woodbury formula, with a cost cubic on the number of instances. Switching the latter once the tree exceeds a critical depth gives a much faster algorithm. The idea applies also to the traditional CART or M5 algorithms, and to forests with linear leaves.
The argument be applied to other types of trees, whenever the optimization of node (whether a leaf or a decision node) can be computed in superlinear time of the number of instances. We exploring this, particularly with low-rank linear mappings, which are more parsimonious than regular linear mappings.
10

---

Acknowledgments and Disclosure of Funding
Work supported by NSF award IIS-2007147.
References
[1] T. Akiba, S. Sano, T. Yanase, T. Ohta, and M. Koyama. Optuna: A next- next-generation hyperpa- rameter optimization framework. In Proc. of the 25th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (SIGKDD 2019), pages 2623 2631, Anchorage, AK, Aug. 4-8 2019.
[2] J. Bergstra, D. Yamins, and D. Cox. Making a science of model search: Hyperparameter opti- mization in hundreds of dimensions for vision architectures. In S. Dasgupta and D. McAllester, editors, Proc. of the 30th Int. Conf. Machine Learning (ICMI 2013), pages 115-123, Atlanta, GA, June 16 21 2013.
[3] L.. J. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth, Belmont, Calif., 1984.
[4] M. A. Carreira-Perpiñán and K. Gazizov. The tree autoencoder model, with application to hierarchical data visualization. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Pa- quet, J. Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems (NeurIPS), volume 37, pages 32281-32306. MIT Press, Cambridge, MA, 2024.
[5] M. A. Carreira-Perpiñaa and P. Tavallali. Alternating optimization of decision trees, with appli- cation learning sparse oblique trees. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems (NeurIPS), volume 31, pages 1211-1221. MIT Press, Cambridge, MA, 2018.
[6] M. Á. Carreira-Perpiñán, M. Gabidolla, and A. Zharmagambetov. Towards better decision forests: Forest Alternating Optimization. In Proc. of the 2023 IEFE Computer Society Conf. Computer Vision and Pattern Recognition (CVPR (33,, pages 7589-7598, Vancouver, Canada, June 18-22 2023.
[7] R.-E. Fan, K.-W Chang, C.-J. Hsieh, X.-R. Wang, and C.-J. Lin. LIBLINEAR: A library for large linear classification. J. Machine Learning Research, 9:1871-1874, Aug. 2008.
[8] M. Gabidolla and M. Á. Marreira-Perpinhal Pushing the envelope of gradient boosting forests via globally-optimized oblique trees. In Proc. of the 2022 IEEE Computer Society Conf. Com- puter Vision and Pottern Recognition (CVPR'22), 22), pages 285-294, New Orleans, LA, June 19- 24 2022.
[9] M. Gabidolla and M. Á. Carreira-Perpiñann Optimal interpretable clustering using oblique decision In Proc. of the 28th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (SIGKDD 2022), pages 400-410, Washington, DC, Aug. 14-18 2022.
[10] G. H. Golub and C. F. van Loan. Matrix Computations. Johns Hopkins University Press, fourth edition, 2012.
[11] G. Guennebaud, B. Jacob, et al. Eigen v3. Cictps///eigga..uuufaaal....... 2010.
[12] J. Hastie, R. Tibshirani, and H. Friedman. The Elements of Statistical Learning Data Mining, Inference and Prediction. Springer Series in Statistics. Springer-Verlag, second edition, 2009.
[13] R. A. Horn and C. Johnson. Matrix Analysis. Cambridge University Press, second edition, 2013.
[14] L. Hyafil and R. L. Rivest. Constructing optimal binary decision trees is NP-complete. Infor- mation Processing Letters, 5(1):15-17, May 1976.
[15] Y. LeCun, I.. Bottou, Y. Bengio, and Haffner. Gradient-based learning applied document recognition. Proc. IEFF, 86(1 1):2278-22222 Nov. 1998.

---

[16] M. Lichman. UCI machine learning repository. http://archive. ics wct..uci..o edu/mlmm/l ml 2013.
[17] W.-Y Loh. Fifty years of classification and regression trees. International Statistical Review, 82(3):329-348 (with discussion, pp. 349-370), Dec. 2014.
[18] G. Loosli, S. Canu, and L. Bottou. Training invariant support vector machines using selective sampling. In L. Bottou, O. Chapelle, D. DeCoste, and J. Weston, editors, Large Scale Kernel Machines, Neural Information Processing Series, pages 301-320. MIT Press, 2007.
[19] J. R. Quinlan. Learning with continuous classes. In A. Adams and L. Sterling, editors, Proc. 5th Australian Joint Conf. on Artificial Intelligence (AI'92), pages 343-348, 1992.
[20] R. Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann, 1993.
[21] L. Rokach and Maimon, Data Mining With Decision Trees. Theory and Applications. Num- ber 81 in Series in Machine Perception and Artificial Intelligence. World Scientific, second edition, 2015.
[22] M. van den Bos, J. G. M. van der Linden, and E. Demirović. Piecewise constant and linear regression trees: An optimal dynamic programming approach. In R. Salakhutdinov, Z. Kolter, K. Heller, A. Weller, N. Oliver, J. Scarlett, and F. Berkenkamp, editors, Proc. of the 41th Int. Conf. Machine Learning (ICML 2024), pages 48994 49007, Vienna, Austria, July 21-21 2024.
[23] S. Vijayakumar and S. Schaal. Local adaptive subspace regression, Neural Processing Letters, 7(3):199-149, 1998.
[24] Y. Wang and I. H. Witten. Induction of model trees for predicting continuous classes. Working Paper 96/23, Dept. of Computer Science, University of Waikato, New Zealand, Oct. 1996.
[25] H. Witten, E. Frank, M. A. Hall, and C. J. Pal. Data Mining: Practical Machine Learning Tools and Techniques. Morgan Kaufmann,, fourth edition, 2016.
[26] H. Xiao, K. Rasul, and R. Vollgraf. Fashion-MNIST: A novel image dataset for benchmarking machine learning algorithms. 1rXiv.1708.07777,,5pp 15 2017.
[27] A. Zeileis, T. Hothorn, and K. Hornik. Model-based recursive partitioning. Journal of Compu- tational and Graphical Statistics, 17(2):92-554,, 2008
[28] A. Zharmagambetov and M. A. Carreira-Perpiñán Smaller, more accurate regression forests using tree alternating optimization. In H. Daumé III and A. Singh, editors, Proc. of the 37th Int. Conf. Machine Learning (ICML 2020), pages 1 11398-11408, Online, July 13-18 2020.
[29] A. Zharmagambetov and M. Á. Marreira-Perpiñáal Semi-supervised learning with decision trees: Graph Laplacian tree alternating optimization. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and Oh, editors, Advances in Neural Information Processing Systems (NeurlPS), volume 35, pages 2392-2405. MIT Press, Cambridge, MA, 2022.
[30] A. Zharmagambetov, S. S. Hada, M. Gabidolla, and M. Á. Carreira-Perpint Non- Non-greedy algorithms for decision tree optimization: An experimental comparison. In Int. J. Conf. Neural Networks (IJCNN'2I) 2I), Virtual event, July 18-22 2021.
12

---

A
Algorithm
The algorithm is iterative procedure that optimizes tree nodes depthwise fashion until conver- gence. Each node is trained on its corresponding reduced set R; C (1...., N). Decision nodes learn to route training samples the leaves where they achieve the lowest error, while leaves are trained as standard regression models. The pseudocode for the modified TAO algorithm is provided fig.
input training set {xn) ) x=
regularization hyperparameters À 2 0, 2 0; initial tree T(; () of depth A,
where θ = w, who HED U [A byljec .o.....NNS <- nodes depth O..... A, respectively
for each i E A: generate R, (instances that reach node i)
repeat
for d = A down to 0 (par)for i E Na if E C. then
(A,, b:) +- ridge regression solution
on R, with penalty (see Theorem 3.3 in the main paper)
else
for each instance Xn generate pseudolabels Tin and sample weights "/in [w; w + fit fz-regularized weighted binary classifier on {(x,, Yin Vin MERR. with penalty (see Theorem 3.2 in the main paper)
for each i E N: update R, on tree T until stop return T
Figure 3: Pseudocode for the modified TAO algorithm with linear leaf optimization.
13

---

Table 3: Summary of datasets used in the experiments. N denotes the number of samples, D the input dimensionality, E the output dimensionality, and A the critical depth.
Dataset
N
D
E
A
ailerons
7154
40
CT slice
32100
384
SARCOS
44484
21
Rotated MNIST
60000
784
784
Patched Fashion MNIST
60000
784
64
Random MNIST
60000
784
Infinite MNIST
1000000
784
784
10
B Dataset description
Dataset characteristics are summarized Table 3
ailerons A dataset where the attributes describe the status of air- craft. The task to predict the control signal applied to the ailerons. https://wwwt w.c...c..ur
Saaarggg/RegresiiaaDaaattttttt html
CT slice A dataset from the UCI repository [16]. Each slice is represented by two polar histograms capturing bone structures and air inclusions, concatenated into 384-dimensional feature vector. The target is the relative position of the slice along the axial axis. https://archive. ics. uci. edu/datasets
SARCOS A robotics dataset used in 23 where the task to predict joint torques from 21 input features including joint positions, velocities, and accelerations. http: /tt:://wwww.ee. www.gsssssusssssss..... org/ gegggggmm//aa///
Rotated A regression task in which MNIST 15 digits rotated by class-specifes angles. The goal is to predict rotated image from the original image. The rotation degrees are: O: 8 1: 49,, 2: -57 -63, 4: 16",
18% 6: 10 7: 322. 711. 9: 58%.
Patched Fashion MNIST A regression task where the model predicts an 8 x 8 patch extracted from Fashion MNIST (66 image. The patch location depends the digit label, with top-left corners positioned as follows: O: (17, 6), 1: (10, 19), 2: (17, 18), 3: (6, 0), 4: (2, 16), 5: (13, 12), 6: (10, 0), 7: (O, 10), (), 9: (11, 11).
Random MNIST A synthetic regression task where MNIST [15] digits are linearly mapped to single scalar value using class-specific random projections. The goal is predict this value from the original image.
Infinite MNIST 188 An augmented version of MNIST containing million synthetically gener- ated digits using aseudo-random deformations and translations. Each image is linearly mapped a single scalar value using a class-specific projection, and the task is to predict this value. https://leon botto.. wttp:rooccsss/iininiiii.m
14

---

C Grid-search hyperparameter optimization
We provide an extended version of Table from the main text, which also includes results for the CTSSice dataset.
Table 4:
Hyperparameter search time and final model training time on the Patched Fashion MNIST and CTSlice datasets. denotes the depth of the final selected model, chosen from a regularization path that started at depth 15 for TAO and from fully-grown tree for CART-linear.
Train RMSE
Test RMSE
Search time, $
Training time, 8
Dataset
Model
TAO adap.
10
0.11
0.16
3485.38
253.82
TAO naive
10
0.11
0.16
6899.90
256.05
Patched
CART-lin. adap.
17
0.09
0.19
350.37
45.79
MNIST
CART-lin. naive
17
0.09
0.19
2444.19
54.08
TAO adap.
0.44
1.51
548.92
62.65
TAO naive
11
0.21
1.76
741.49
73.83
CTSlice
CART-lin. adap.
0.14
2.75
116.90
4.60
CART-lin. naive
31
0.14
2.69
1460.53
5.61
15

---

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:
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 can be expected to generalize other settings.
It is fine to include aspirational goals motivation long it 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 paper admits that experiments are limited to sequential computation setting. Additionally, the computational complexity analysis assumes a balanced tree and uniform data distribution across leaves, conditions that may not hold in practical applica- tions.
Guidelines:
The answer NA means that the paper has no 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 au- thors should reflect on how these assumptions might be violated 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 a few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or a speech-to-tex system might not be used reliably to provide closed captions for online lectures because 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 ad- dress 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 It 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 proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?

---

Answer: [Yes]
Justification:
Optimization algorithm and Analysis of the computational complexity sec-
tions
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 in the statement of any theo- rems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
supplementary material
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
also be provided via
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to re- produce 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 au- thors are welcome to deseribe 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 (e.g.. to registered users), but it should be possible for other researchers have some path reproducing or verifying the results. 5. Open access to data and code

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification:
We plan to make available code in the future.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see
the NeurlPS code and
data submission guidelines for more de-
tails.
While encourage the release of code and data, understand that this might not be possible, so "No" am acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines luttps://nips.co ccs www.cccppccc..ccc.cccccccc.oolel ceabbicc/uiieen get////idee//ee// SarteeSumiissiooPoee
for more details. The authors should provide instructions 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, to 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 (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experiment section and supplementary material Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper 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 other appropri- ate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification:
Results are averaged over multiple runs with error bars shown.
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, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror 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).
18

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the enror bar is the standard deviation or the standard error of the mean.
is OK to report 1- 1-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, 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 are out of range (c.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables 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: Supplementary material
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, 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 in the paper (e.g., preliminary failed experiments that didn't It make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https/ssttt/t/tusssssssc/// http:///oorpp..cccaaaaaaccttcatt
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification:
The paper proposes an algorithmic speedup for training decision trees.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
19

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is 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 being used as 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 mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to 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 models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses 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 re- quiring that users adhere usage guidelines or restrictions 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
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?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not existing assets.
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 (c.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.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, patdess.pppssiiispae thcode. com/ datasete has curated licenses for some datasets. Their licensing guide can help determine the cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
20

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification:
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 contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, cura- tion, 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
Question: Does the paper deseribe 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?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and 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 as the institution conducting the review.
16. Declaration of LLM usage
21

---

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 used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [No]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
22


Reviews:
[{"review_id": "YpvAXvjA7Z", "reviewer": "Reviewer_UDF8", "summary": "This paper closely examines the Tree Alternating Optimization(TAO) algorithm for regression trees with linear leaves, which was introduced in an ICML 2020 paper [1]. TAO supposedly provides trees that are \"much smaller and much more accurate\" than those produced by other older popular algorithms like CART. This is believable and I did not verify the results from the ICML 2020 paper. TAO iterations consist of two types of steps, those optimizing the internal decision nodes of the tree, and those optimizing the leaf nodes. The leaf node optimization step is essentially the same as solving a ridge regression problem for the data points sent to that particular leaf. In the original paper introducing TAO, they perform a \"naive\" ridge regression whereas in this submission, they show that they can substantially speed up this step (at least for higher dimensionality of the data and/or higher tree depth) using the Sherman-Morrison-Woodbury formula. Basically, the trees produced by the algorithm provided in this paper are identical to those produced by TAO but they can compute them faster. The submission shows improved computational complexity by some basic analysis and furthermore they also experimentally show that their algorithm is faster than TAO.\n\nReferences:\n1) \"Smaller, more accurate regression forests using tree alternating optimization\" by A. Zharmagambetov and M. Á. Carreira-Perpiñán, ICML 2020", "questions": "Minor typos/clarifications:\n\nLines 54-58: I believe you want to mention $N'$ here instead of $N$ where $N'$ is the effective sample size $N2^{-\\Delta}$, which you mention at Line 240. Since you are using $N$ for the size of the dataset in the immediately preceding lines in this paragraph from Lines 47-53, it gets a bit confusing here.\n\nLine 56: but -> by\n\nLine 113: peocedure -> procedure", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Quality: The submission is technically sound with claims that are well-supported by both theoretical results and experimental validation. The methods used are appropriate and this is a complete piece of work.\n\nClarity: The submission is overall clearly written with minor typos which I list in the *Questions* section of the review.\n\nSignificance: The submission is certainly relevant to NeurIPS as work on regression trees has been appearing at NeurIPS and other related conferences for several decades. Yes, others are likely to build on this work and it is a clear improvement over the prior work on TAO. \n\nOriginality: I think this is the major weak point of this submission. My main qualm is whether the particular contribution of this submission warrants a separate NeurIPS (which is supposed to be one of the top venues) publication. Ideally, if the authors of the ICML 2020 paper had noticed this particular improvement in the work they had submitted then, it would have merited maybe only a paragraph discussion in that original paper with the rest of it pushed to the Appendix. Also, I believe the particular idea of using the Sherman-Morrison-Woodbury formula to speed up regression has cropped up in many other prior papers. But I agree that it is not something which the TAO paper used so this is novel when restricted to the TAO algorithm.", "was_revised": true, "final_justification": "I have considered the author's rebuttal regarding originality and also gone over the NeurIPS 2025 reviewer guidelines regarding originality where it is stated that: **As the questions above indicates, originality does not necessarily require introducing an entirely new method. Rather, a work that provides novel insights by evaluating existing methods, or demonstrates improved efficiency, fairness, etc. is also equally valuable.**\n\nThe paper clearly demonstrates improved efficiency and so I feel its major weakness of Originality that I held previously is not so strong. But I still feel that it is a borderline paper and so I am only increasing my score to Borderline accept from my earlier score of Borderline reject.", "rebuttal": "Thanks for your clear review.\n\n**Originality**: our use of the SMW formula may seem obvious in hindsight, but: 1) the authors of the ICML 2020 paper did not realize this for the TAO algorithm, as you note; 2) the many researchers working since the 1980s on the case of CART linear trees did not realize either; and 3) as noted by reviewer 5aDC, we provide a \"nontrivial new insight that yields a significant practical gain\", since the speedup is large and doesn't involve any approximation, for both TAO or CART. We have added results to speed up CART linear trees in the table in the reply to reviewers 5aDC.\n\nAlso, our paper has a second contribution: the non-monotonic behavior of the training complexity predicted by our analysis, very unusual in machine learning models. As reviewer 5aDC notes: \"Surprisingly, making the tree deeper beyond can reduce total training time, even though the model has more parameters\"."}, {"review_id": "H8ch001nhV", "reviewer": "Reviewer_hbbP", "summary": "The paper proposes an enhancement to the TAO (tree alternating optimization) algorithm for training regression trees with linear leaves. Specifically, they propose to optimize the leaves’ linear models using the Sherman-Morrison-Woodbury formula, taking advantage of the fact that each leaf only receives a potentially small subset of the full training set. On sufficiently deep trees, this has the potential to lead to significant speed ups, an observation that is verified experimentally across seven datasets.", "questions": "No specific questions, but please see weaknesses above.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- A simple improvement to speed-up the computation of linear regression models in the leaves of TAO regression trees\n- The paper provides a clear analysis of the complexity of the proposed improvement\n- Experiments show clear speed-ups over standard TAO\n\n----\n\nWeaknesses:\nWhile the paper proposes a nice improvement that can speed up the computation of regression trees with high dimensionality, I found the paper to have limited novelty and limited significance.\n- Limited technical novelty: TAO is well known algorithm Section 3 is a description of previous work primarily. The main change is the application of the SMW formula to solve the leaf problem faster in the “deep regime”.\n- The experimental results show clear speed-up in performance, however significant gains are saved for very high-dimensional datasets with sufficiently deep trees such that the number of instances reaching a given leaf is smaller than the dimensionality. Gains in ensemble settings are more modest relatively.\n- Deeper trees lead to reduced RMSE on training set, but do not necessarily generalize better as they may overfit. The experiments in the paper are not focused on generalization and investigation of whether the observed gains (that are focused on deep trees) are useful in practice.\n- The work focuses on TAO regression trees exclusively. While the paper note that the main argument can be used to speed up greedy recursive partitioning algorithms such as CART, there is no experimental results demonstrating this. Further, the paper notes that this may extend to other types of trees but there is no additional information, examples, or experiments provided to substantiate this.\n- Overall, while the contribution in the paper seems correct and potentially useful in some settings, it seems to me very incremental with relatively limited significance.\n\n- minor:\n* “Gram matrix” is used in Section 5 but is not previously defined.\n* it would nice to have add y-axis labels to Fig 1 (especially as it seems the label for right-most figures is not the same as the rest?).", "was_revised": true, "final_justification": "Given the additional results provided by the authors in the discussion period that demonstrate the empirical gains of the proposed approach in a hyper-parameter tuning setting, I have increased my score. I still feel that the paper has limited technical novelty, as also noted by the other reviewers.", "rebuttal": "Thanks for your insightful comments.\n\n**Limited novelty and limited significance**: our use of the SMW formula may seem obvious in hindsight, but: 1) the authors of the ICML 2020 paper did not realize this for the TAO algorithm; 2) the many researchers working since the 1980s on the case of CART linear trees did not realize either; and 3) as noted by reviewer 5aDC, we provide a \"nontrivial new insight that yields a significant practical gain\", since the speedup is large and doesn't involve any approximation, for both TAO or CART. We have added results to speed up CART linear trees in the table in the reply to reviewers 5aDC.\n\nAlso, our paper has a second contribution: the non-monotonic behavior of the training complexity predicted by our analysis, very unusual in machine learning models. As reviewer 5aDC notes: \"Surprisingly, making the tree deeper beyond can reduce total training time, even though the model has more parameters\".\n\n**Significant gains are saved for very high-dimensional datasets with sufficiently deep trees [...] Deeper trees [...] may overfit.** This is one important point that we did note (in line 76 and 281), but is worth enlarging. Since our algorithm does not change the learned trees, hyperparameter tuning and model selection is as with the regular (naive) algorithm. We simply do a grid search over the hyperparameters; typically, we set the tree depth $\\Delta$ to large enough (say, 15), vary the regularization hyperparameters $\\lambda$ and $\\alpha$, and pick the model with lowest validation error (when varying $\\lambda$, the tree will progressively shrink, as noted above, automatically spanning a range of depths). As with any grid search, some of those trees will overfit and some will underfit, and the selected model may be shallow enough that the improved algorithm does not speed up that particular tree. But we don't know that until we do the grid search (in fact, it could be that the selected tree does show a large speedup). But, regardless of what the selected tree is, the grid search should span a range of depths so that we can corner the model with lowest validation error, and some of those depths (the larger ones, which have many linear leaves) will exhibit a large speedup. In short, the total training time (over the whole regularization path) is guaranteed to be significantly sped up, regardless of how shallow the selected model is. We illustrate this in the table in the response to reviewer 5aDC. This now shows the speedup for the selected tree (rather than a deep tree) and the for the whole regularization path (grid search). As you can see, a standard grid search 1) will estimate the tree with lowest validation error (as with any other type of model), and 2) will always involve deep enough trees where the speedup is significant (even if the selected tree is shallow). Thus, in practice there will always be a significant speedup over the grid search."}, {"review_id": "90uHdxKZg9", "reviewer": "Reviewer_5aDC", "summary": "This paper proposes a faster training algorithm for oblique regression trees with linear predictors in the leaves, based on the Tree Alternating Optimization (TAO) framework. The authors modify the leaf-fitting step by applying the Sherman–Morrison–Woodbury (SMW) formula to invert an $N \\times N$ matrix instead of a $D \\times D$ one, where $N$ is the number of instances reaching a leaf and $D$ is the feature dimension. This results in an exact but significantly faster solution.\n\nThe key insight is that for deep trees exceeding a critical depth $\\Delta^* = \\log_2(N/D)$, each leaf receives fewer than $D$ samples, making SMW-based inversion more efficient. Surprisingly, making the tree deeper beyond $\\Delta^*$ can reduce total training time, even though the model has more parameters.\n\nThe authors analyze the complexity and demonstrate substantial speedups (up to $25\\times$) on high-dimensional ($D=2500$) regression tasks, with identical predictive performance to the original TAO algorithm.", "questions": "**1. Scope of Experiments:** Have you considered comparing your approach to other linear-tree algorithms, such as XGBoost or Random Forests? Even though those methods follow a different (greedy) strategy, it would be informative to see how TAO (with your speedup) compares in terms of speed and accuracy on benchmark tasks.  \n**2. Hyperparameter Tuning:** TAO requires setting the tree depth and regularization strength. Since deeper trees become “cheaper to train” in your approach, do you recommend always searching for depths beyond the critical threshold? Is there a risk of overfitting when training very deep trees? How do these hyperparameters influence performance in practice?  \n**3. Imbalanced Leaves:** The paper mainly analyzes balanced trees. How does the performance behave when the tree is highly unbalanced?", "limitations": "The paper does not explicitly discuss limitations. Some of the method’s limitations are mentioned above.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n1. The contributions of the paper are clearly stated (an exact faster leaf step, complexity analysis, experiments). The paper builds on the known TAO algorithm but identifies a nontrivial new insight that yields a significant practical gain.\n2. Faster training of linear-model trees is useful for regression tasks, especially since TAO-trained trees can sometimes outperform greedy methods such as CART and M5 in accuracy. The proposed idea also applies to other tree-learning methods, as the authors note.\n3. The use of the SMW identity is mathematically sound and yields exact equivalence to the original leaf solution. The derivations and complexity arguments are detailed and appear correct.\n4. The paper provides a careful time-complexity analysis, covering both “shallow” and “deep” regimes, and clearly explains why a deep tree can be faster to train than a linear model.\n5. The experiments on real and synthetic data demonstrate large speedups without loss of accuracy. \n\n\n**Weaknesses:**\n1. The main idea (use SMW for faster inversion) follows naturally from the observation that deeper trees have smaller leaf sample sizes. While the approach is effective, it builds on known mathematical tools and does not introduce a fundamentally new learning paradigm, but rather an optimization applied to TAO.\n2. The paper lacks an explicit discussion on limitations. The proposed method inherits all the limitations of TAO. Namely, TAO optimizes a tree of given structure (depth and topology). The structure is initialized often as a full binary tree, and TAO only optimizes the parameters, not the structure. This leads to hyperparameter sensitivity, and poor initialization or overly deep/shallow structures can result in significant overfitting or degraded performance. Additionally, while TAO forests can be smaller overall, individual trees can be quite heavy (because both the splitting functions and the leaf models contribute substantial parameter counts). This is one reason why TAO training can be significantly slower than greedy methods such as CART or M5.\n3. All experimental results focus only on TAO (adaptive) versus TAO (naive). No comparisons are shown against other linear-tree methods (e.g., CART, M5, or more recent PILOT [1]). The authors cite the TAO paper [2] to state that greedy trees have worse accuracy, but TAO is sometimes significantly slower. Since this paper accelerates TAO, it would be highly relevant to compare TAO (adaptive) to algorithms like XGBoost and Random Forests, as was done in the TAO paper [2]. \n4. The paper primarily discusses balanced trees. It would be helpful to discuss how the method performs on highly imbalanced splits.\n\n**Reproducibility.** The authors do not mention whether they plan to release code or a library. No code archive is attached to this submission.\n\n*[1] J. Raymaekers, P.J. Rousseeuw, T. Verdonck, and R. Yao. Fast linear model trees by PILOT. Machine Learning 113:6561–6610, 2024.*   \n*[2] A. Zharmagambetov, M. Carreira-Perpinan. Smaller, more accurate regression forests using tree alternating optimization. Proceedings of the 37th International Conference on Machine Learning, PMLR 119:11398–11408, 2020.*", "was_revised": true, "final_justification": "My concerns were partially addressed in the authors’ rebuttal, particularly regarding hyperparameter tuning (Q2) and imbalanced leaves (Q3). However, two major concerns remain, as noted in my official response: (1) the level of technical novelty, and (2) the breadth of the experimental study.\n\nGiven the improvements in the rebuttal, I am raising my score to 4. I am willing to raise it further, especially if other reviewers agree on the technical novelty of the contribution.", "rebuttal": "Thanks for your insightful questions.\n\n**Weakness 2.** Since our improved algorithm speeds up the training but does not change the learned tree, you are right that the limitations of linear trees and the original TAO algorithm do continue to apply; we'll note that in the paper. However, TAO does learn the structure to some extent, because (depending on the hyperparameter $\\lambda$ in eq. (1), the weight vector of some decision nodes becomes zero and that node can be pruned (if $\\lambda$ is large enough, the tree is pruned to a single leaf node). Thus, the resulting structure is a subset of the initial tree, and that structure is generally imbalanced. Also, you note that overly deep trees can result in significant overfitting; this is true, but the grid search will not select those.\n\n**Q2.** Hyperparameter tuning. This is one important point that we did note (in line 76 and 281), but is worth enlarging. Since our algorithm does not change the learned trees, hyperparameter tuning and model selection is as with the regular (naive) algorithm. We simply do a grid search over the hyperparameters; typically, we set the tree depth $\\Delta$ to large enough (say, 15), vary the regularization hyperparameters $\\lambda$ and $\\alpha$, and pick the model with lowest validation error (when varying $\\lambda$, the tree will progressively shrink, as noted above, automatically spanning a range of depths). As with any grid search, some of those trees will overfit and some will underfit, and the selected model may be shallow enough that the improved algorithm does not speed up that particular tree. But we don't know that until we do the grid search (in fact, it could be that the selected tree does show a large speedup). But, regardless of what the selected tree is, the grid search should span a range of depths so that we can corner the model with lowest validation error, and some of those depths (the larger ones, which have many linear leaves) will exhibit a large speedup. In short, the total training time (over the whole regularization path) is guaranteed to be significantly sped up, regardless of how shallow the selected model is. We illustrate this in the table below.\n\n**Q1.** Scope of Experiments. In the table below, we report other baselines you noted (XGBoost, RF, CART with linear leaves (M5)) and also the runtime for 1) the whole regularization path and 2) the selected tree (having lowest validation error).\n\nWe conduct new experiments on the Patched Fashion MNIST dataset ($N=60000$, $D=784$, $E=64$, and the critical depth $\\Delta^* = 6$) to provide the requested baseline comparisons and demonstrate the practical advantages of our method.\n \n*Experimental setup:* For the TAO and the CART baseline, we performed a hyperparameter search by constructing their respective regularization paths:\n- For TAO, we start with a complete balanced tree of depth 15 and increase the regularization parameter $\\lambda \\in [0.01, 1000]$, progressively pruning the tree at each step. We use warm-start, initializing each step from the previous tree.\n- For CART, we use the cost-complexity pruning path generated by scikit-learn's `cost_complexity_pruning_path` function.\n\nWe compare our adaptive TAO against naive TAO, adaptive/naive CART-linear, Random Forest (default hyperparameters), and XGBoost (default hyperparameters). The reported time for CART models includes both initial tree construction and cost-complexity pruning.\n\nThe table below shows the performance of the final selected model (chosen by lowest validation error) and the running time for both the whole regularization path and the final model training.\n\nModel | Final $\\Delta$ | Train RMSE | Test RMSE | Number of leaves | Training time, s (whole regularization path) | Training time, s (selected tree)\n-|-|-|-|-|-|-\nTAO adaptive | 10 | 0.11 | 0.16 | 68 | 3485.38 | 253.82\nTAO naive | 10 | 0.11 | 0.16 | 64 | 6899.90 | 256.05\nCART-linear adaptive | 17 | 0.09 | 0.19 | 642 |350.37 | 45.79\nCART-linear naive | 17 | 0.09 | 0.19 | 642 | 2444.19 | 54.08\nRandom Forest | 47 | 0.06 | 0.18 | 3791335 | | 2734.23\nXGBoost | 6 | 0.11 | 0.17 | 382313 | | 2117.93\n\nNote: For RF and XGBoost, \"Final $\\Delta$\" is the maximum depth and \"Number of leaves\" is the total number of leaves across all trees in the ensemble.\n\nThese experiments demonstrate:\n- TAO tree achieves the best test RMSE of 0.16, outperforming strong baselines like XGBoost and Random Forest.\n- The whole regularization path for the adaptive TAO is ~2x faster than the naive implementation. The speedup is even more pronounced for adaptive CART-linear, at ~7x faster. This confirms that our method provides a significant practical advantage by accelerating the entire model selection process, which must evaluate many deep trees, regardless of how deep the final selected model is.\n\nWe will report similar experiments for the other datasets in the final paper.\n\n**Q3.** Imbalanced leaves. The trees learned by TAO and reported in our experiments (in the table above and in the paper) actually show significance imbalance. This is because 1) as noted above, the learned tree undergoes automatic pruning, so it is not complete, and 2) the reduced set of each leaf (set of training instances that reach it) need not be uniform even in a complete tree. For example, in the tree listed in the table above the reduced set sizes ranged from a maximum of 5649 to a minimum of 8 instances. Thus, although our complexity analysis considers the balanced case (which has the fastest runtime), the experiments show real-life results, which are far from balanced, yet the speedup is significant. We'll make this clear in the paper."}, {"review_id": "plVCNmGjzr", "reviewer": "Reviewer_U6L7", "summary": "The authors focus on learning oblique regression trees (with linear leaves). They propose a tweak to the TAO algorithm that speeds up training for deep trees. This tweak is exact and makes use of the fact that fitting a linear model at a leaf uses few samples, often making the rank of the data matrix constrained by the number of samples rather than the number of features. This yields a speedup, which the authors provide a complexity analysis for and confirm numerically.", "questions": "Can the authors provide more in-depth exploration of when the speed-up applies and how it relates to a model's predictive performance / overfitting?\n\nCan the authors discuss in more detail how the method could be extended to other settings, e.g. learning sparse or axis-aligned splits? classification trees?", "limitations": "The Limitations are not explicitly discussed in the Conclusion section, might be nice to discuss them more carefully there, esp how the speed-up relates to tree depths.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "- S1: The authors propose an exact improvement to the TAO algorithm that can often provide a speed-up\n- S2: The algorithm is intuitive, simple, and straightforward to implement\n- S3: The experiments confirm the speed-ups, especially for deep trees\n- W1: The impact of the speed-up is unclear, as it tends to kick in for large depths or limited-sample regimes where decision trees may tend to overfit. Speed & performance comparisons to other algorithms (including greedy methods like CART) would be helpful to show that there are realistic settings where this speed up applies & yields strong performance.\n- W2: The introduction of the method and analysis of its complexity (Sec 3 & 4) are perhaps overly detailed for introducing the usage of the SMW formula, a fairly well-known trick\n- W3: For a paper like this that focuses on an efficiency improvement, it would be nice to see code provided", "was_revised": true, "final_justification": "I thank the authors for their clarifications, but maintain my score of 4. I am still not convinced that a standard grid search will always involved deep enough trees to show a significant speedup, i.e. if a modest-depth tree overfits the data there is no need to search deeper trees.", "rebuttal": "Thanks for your comments.\n\n**W1 and Q1.** We refer you to the reply \"Q2. Hyperparameter tuning\" and \"Q1. Scope of Experiments\" to reviewer 5aDC. There, we explain that a standard grid search 1) will estimate the tree with lowest validation error (as with any other type of model), and 2) will always involve deep enough trees where the speedup is significant (even if the selected tree is shallow). Thus, in practice there will always be a significant speedup over the grid search.\n\n**Q2**. Learning sparse splits: we already do this ($l_1$ term in eq. 1). Learning axis-aligned splits: this simply changes the reduced problem over a decision node to enumerating over features and thresholds (rather than fitting a linear classifier). Our speedup continues to happen in the leaves. Learning classification trees: we have not done this because it requires training a linear softmax classifier in each leaf; the SMW formula may still be useful there."}]

Author rebuttal:

Meta-review: The paper proposes a faster training algorithm for regression trees with linear predictors in the leaves, based on the TAO (tree alternating optimization) framework. The enhancement is based on optimizing the leaves' models using the Sherman-Morrison-Woodbury formula to reduce the size of the matrix that needs to be inverted. The paper provides experiments demonstrating large speedups on real and synthetic data.

Overall, the paper proposes a clever use of a technique, which leads to meaningful practical speedups. The main weakness is that the technical novelty is somewhat limited, as it is essentially a (nontrivial) modification of TAO.
Decision: Accept (poster)