Regression Trees Know Calculus
Authors: Nathan Wycoff
Venue: NeurIPS 2025 poster ()
Keywords: regression tree
gradient learning
interpretability
variable importance
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: Use differences between means in tree splits to estimate function derivatives; now we have gradient-based methods for trees.

Abstract: Regression trees have emerged as a preeminent tool for solving real-world regression problems due to their ability to deal with nonlinearities, interaction effects and sharp discontinuities. In this article, we rather study regression trees applied to well-behaved, differentiable functions, and determine the relationship between node parameters and the local gradient of the function being approximated. We find a simple estimate of the gradient which can be efficiently computed using quantities exposed by popular tree learning libraries. This allows tools developed in the context of differentiable algorithms, like neural nets and Gaussian processes, to be deployed to tree-based models. To demonstrate this, we study measures of model sensitivity defined in terms of integro-differential quantities and demonstrate how to compute them for regression trees using the proposed gradient estimates. Quantitative and qualitative numerical experiments reveal the capability of gradients estimated by regression trees to improve predictive analysis, solve tasks in uncertainty quantification, and provide interpretation of model behavior.

Regression Trees Know Calculus
Nathan Wyeoff
Department of Mathematics and Statistics University of Massachusetts Amherst, MA 01003 anycoff@umase edu
Abstract
Regression trees have emerged as a preeminent tool for solving real-world regres- sion problems due to their ability to deal with nonlinearities, interaction effects and sharp discontinuities. In this article, we rather study regression trees applied to well-hehaved, differentiable functions, and determine the relationship between node parameters and the local gradient of the function being approximated. We find simple estimate of the gradient which can be efficiently computed using quantities exposed by popular tree learning libraries. This allows tools developed in the context of differentiable algorithms, like neural nets and Gaussian processes, to be deployed to tree-based models. To demonstrate this, we study measures model sensitivity defined in terms of integro-differte differential quantities and demonstrate how to compute them for regression trees using the proposed gradient estimates. Quantitative and qualitative numerical experiments reveal the capability of gradi- ents estimated by regression trees to improve predictive analysis, solve tasks uncertainty quantification, and provide interpretation of model behavior.
Introduction
Tree-based methods, such as regression trees, are a workhorse of the contemporary data scientist. Their case of use, computational efficiency and predictive capability without the need for extensive feature engineering makes them popular with practitioners. The most widely used version of regression trees approximate with greedily constructed, piecewise-constant functions than can handle data which exhibit discontinuities or divergent behavior in various parts of the feature-space. Perhaps because of their capability tackle pathological problems, seems that some of their properties in approximating well-behaved functions may have gone unnoticed.
In this article, will study the approximation of well-behaved differentiable function on the unit cube in dimension P with a piecewise constant regression tree. In particular, we will investigate means of approximating V using only information contained in the tree structure computable in single pass through the tree. We find simple and easily computable quantity analogous to a finite difference and use rapidly form estimates of integro-differente quantities. Previously, gradient estimation in regression trees has been studied in the context where the leaves have differentiable models, and the gradients of these models are used to estimate the gradient (e.g. Chaudhuri al. (1995); ; Loh (201T)). However, the constant-leaf tree remains prevalent in practice, and the purpose of this article rather to examine the implicit gradient estimation that occurs within these constant- trees where, formally, the gradient of the tree is almoot-everywiae zero.
With gradient estimator in hand, unlock for tree-based models the stable of existing gradient- based methods for variable interpretation and dimension reduction developed in other areas. Among many possibilities, we will study particular the Active Subspace Method (Constantine) (0155). a global dimension reduction technique from the Uncertainty Quantification literature, and the
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Function
Depth estimate
Depth estimate
1.0
1.0
10
0.8
0.8
0.8
0.6
0.6
0.6
0.2
0.2
0.0
0.0
0.0
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Depth estimate
Depth estimate
True Vector Field
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.0
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Figure 1: Illustration of Gradient Estimates. The top left gives a target function, and the bottom right gives its gradient vector field. Shown in between estimates of the gradient extracted from regression tree to data from the function converging to the true vector field.
Integrated Gradient Method (Sundararajan et 2017). local model interpretation technique from the neural network literature.
Active Subspaces provide for linear dimension reduction, which is already commonly used in the setting of regressions trees, such as when using random projection or PCA for rotated trees (Breiman 2001 Rodriguez al., (006). In contrast to these methods, however, active subspaces consists of supervised linear dimension reduction which takes the relationship between features and response into account. Already, supervised linear dimension reduction has been proposed for with tree based methods where, c.g. kernel method is used to perform the dimension reduction which is then applied a tree-based method (Shan et al. 2015). But here, we show how actually use the tree itself to perform a linear sensitivity analysis, rather than relying on a helper model to do this. This is essential if the analyst interested in modee-interpreettion (as contrasted with data-inteeppeetation (Chen et al. 2,200), and to the best of our knowledge the application of the Active Subspace method, enabled by our novel gradient estimates, the first such linear sensitivity metric for trees. And while we' ve so far discussed what active subspaces can do for regression trees, we don't 't think this new relationship will be one-sided. Our numerical experiments show that regression trees can serve as scalable estimators of the active subspace, favorable to existing methods in certain circumstances. We hope this can highlight the potential for regression trees in the gradient- -baee UQ space.
We view the major contributions of our article as follows:
1. We study a simple algorithm to extract gradient and integrated gradient information from regression trees.
2. We show how to use this port gradient- based interpretability techniques from other fields to benefit interpretability of regression trees.
3. We find that in certain circumstances estimates of active subspaces than existing UQ methods.
enablee regression trees produce better
We begin in Section by discussing pertinent background on regression trees and gradient-based interpretability. Our main methodological contributions are given in Section 3 and developed theoretically in Section Subsequently, we illustrate these procedures on numerical examples in Section 5 before offering conclusions and future research directions in Section

---

Depth
Dep4h
2.2
12
0.8
0.8
A2
A1
0.5
1
0.5
fx() 2
A2
04
9.4
0.8-0.2
0.6
0
X
0.6
1.0
0.4
64
9.4
0.4
Figure We can extract finite difference gradient approximations from a regression tree by comparing values of adjacent nodes in splits.
2
Background
While small decision trees are easily interpretable, they become significantly less so as they grow in size if they are aggregated via Random Forests (Breiman 2001 2002) gradient boosting (Friedman 2001). Consequently, developing methods for increasing the interpretability of trees is of great importance (Louppe 2014).
2.1 Variable Interpretation and Selection in Regression Trees
Several methods for variable importance were suggested alongside some of the original tree-based methods (Breiman, 2017 2001, 2002), the two most salient for our study being the Mean Decrease in Impurity (called MDI or Tree Weight Kazemitabar et al. (2017)) and the Feature Permutation method. MDI assigns importance to variables in proportion the mean reduction in cost when splitting along a given variable, an intuitively reasonable approach. However, MDI as originally proposed was sensitive to properties of the feature variables as well as the depth within the tree that a split occurred, leading to "debiased" variants (Sandri and Zuccolotto 20088] Li et al. 2019). Kazemitabar al. (2017) well as Klusowski and Tian (2020) studied theoretical properties of a simplified version of this metric using only the first split ("stumps"). On the other hand Feature Permutation is based measuring decrease in performance when shuffling given feature, and though the method does have some desirable properties (Ishwaran (007). it has come under criticism for undesirable behavior in the context of correlated predictors (Hooker et al., 2021 Empirical studies have found issues in both of these methods (Strobl et al. |007] 2008). Against this backdrop of negative results the behavior of these initially suggested methods came contributions in general- purpose machine learning interpretability methods. SHAP values (Lundberg and Lee (017)) have been proposed as a
tool for understanding machine learning models. However, they would prove especially popular for understanding tree-based methods where efficient algorithms have been proposed for estimating these otherwise combinatorially difficult quantities (Lundberg et al.
2019
Karezmarz et al. 2022).
2.2
Gradient-based Model Interpretation
The gradient of function tells how its output is related to its input short distances, and is natural candidate to help explain the behavior of a model. Hechhlinger (2016) suggested to simply look the gradient of model evaluated particular observation gain local understanding. Another approach is the Integrated Gradient (Sundararajan et al. 2017). introduced in the context of neural networks, which involves privileging some setting of input features which called the reference point, which we'll denote x". Subsequently, in order to explain prediction at given point x, we integrate the gradient along the path from x" to x and multiply elementwise against that difference: that is, denoting the output of the neural network as f:
f Ja=D
IG(x) = (x xx)
Vf(ax + (1 aa)a)) a)x")da..
(I)
This theoretically appealing approach has also seen practical success in applications including medicine (Sayres et al. 2019) and chemistry (McCloskey et al. 2019).
3

---

One could also integrate the gradient over larger part of the space to perform a more global sensitivity analysis. This is the idea behind the Active Subspace Method (Constantine 2013). In our context, this involves defining the Active Subspace Matrix as:
- vf(x)VV((x) du(x), C/ c/ 10.11r
(2)
where is a measure. Eigenanalysis on C/44 reveals linear combinations of features which are important, similar to PCA. Various techniques have been developed estimate active subspaces in the presence only of input-output data. A Polynomial Ridge Approximation (PRA) procedure (Hokanson and Constantine, 2018) is available, as is a closed form estimate using Gaussian processes Wycoff et al. (GP: 2021), and also an approach based on neural networks called the Deep Active Subspace Method (DASM: Tripathy and Bilionis 2019
Edeling 2023) has been proposed.
2.3 Variable Importance versus Sensitivity Analysis
Though originating in different academic communities, the ideas of Variable Importance (from the Machine Learning community) and Sensitivity Analysis (from the Uncertainty Quantification community) are closely related. See Antoniadis et al. (202I) for recent review of using regression trees for (ton-gradient-basee
sensitivity analysis. Vannucci al. (2024) explicitly port ideas from the sensitivity analysis literature to enhance variable importance in tree-based methods.
and Maume- Destnnemesssppss (2024) use regression trees to estimate form of sensitivity analysis based on quantiles.
3 Integro-Diiferentiation of Regression Trees
In this section we propose an easily computed estimator of derivatives and integrals of derivatives for regression trees. While the underlying idea is simple, discussing it rigorously requires fair amount of notation; Figure 3 illustrates our notation on a simple regression tree. Say we fit regression tree of depth K to data (Xa. Un = f(x,) +
Gn) with x, [0, 1]" y/ E for n E (1,.... N). and Gn mean zero with finite variance. Purely for simplicity, we will assume that the tree has leaf nodes only at depth K, i.e. there is no path through the tree that ends before depth K. Associate with every node from all depths an integer index i such that the root node is labeled 0 and if node is deeper in the tree than node j. then i j. That is, the indices at depth I are given by {1, 2]. at depth 2 by {3, 4, 5, 6). and generally at depth the indices are given by A&
Figure 3: Illustration of Notation.
In the same example tree as Figure 2 with depth K = 2, examples of notation is as follows: the indices of nodes each depth are Dj = {1,2) and DD2 = {3, 4, 5, 6); the children of node 2 of 5 and of 6; conversely the parent of node 5 is given by Ps = 2; the bounds of node are 1s [0.5, 0) and u = [1, 0.6]: the value of intermediate node 2 is U2 = 0.8 and the value of Icaf node 6 is 0.6; since the "root node" 0 is and since
(2--1 + 1, 1...., 2² For any depth k we define the function B* [0, 1] + .Ax where B* (x) gives the index of the node at depth k which contains x. We denote the variable along which the 7th node splits by o, E {l...., P} and the threshold at which that split occurs as r'. Those points in node for which Vi S -' are mapped to the left child node of i, denoted ci. while those for which Io, > 7 are mapped to the right child node, denoted cf. For each node with child nodes, we denote the mean of the response variable in the left child node by pi and in the right child node by fC. That is. jif gives the average of yn for all n E {1.... N) such that BD,+ (xx,) = of where D; the depth of node (and so D; + 1 the depth of its child nodes).
split along the x-axis, dg nodes and 2 are split along the y-axis, σ 02 2: since the point x lies within the nodes 2 and 5 at depths I and 2 respectively, we have that B² (x) = and (² 5.
3.1 Differentiation
The difference between Øij and pit, which contain the mean of the data on either side of the threshold for node i, contains information about the ot component of the gradient in that area. By dividing this

---

difference proportional to the size of the node along dimension we form quantity similar to finite difference. Let I,, ui denote the extent of node along dimension p for p (l...., P). Then define the following quantity:
71 = 2(1 Bi))
Of n/ 15 Oro:
(x)
(x) Vx E [',
We have used the notation I' = [f..................... [p] to denote the vector of lower bounds of the extent of node i and similar for u', and by [1', u'] we denote the set of points lying within the bounds the 7th node, The ratio V/ contains information about the partial derivative of f with respect to Ia; (which is, again, the variable that node splits along) inside of [1", u'I. The idea that 7 = 0f(x) for any x in node i aue,
only makes sense if the gradient does not vary much within it. We expect this to be the case only for very small nodes, or other words, very deep trees, estimating functions with gradients which vary smoothly; we make this precise in the next section.
At a particular node, we can only form estimates of single partial derivative. However, if our tree is sufficiently deep, we can combine estimates of partial derivatives from nodes at multiple depths to form an estimate of the entire gradient. Recall that N& - {2*-1 + 1,..., 2* contains the index of all nodes of depth k and let P3 denote the index of the parent of node i (which will be a member of 11- Then Algorithm shows how aggregate the partial derivative estimates into a gradient estimate.
Algorithm Tree-Based Gradient Estimation
G + R.P. for all i. for k E {1..... K) do
for E NN do
G + G: {Get parent's estimate]
G. +
200 AD)
{Update along split ]irection]
end for end for
We thus have associated each node with an estimator of the gradient, though if we have not split along a variable p the tree upstream of i, the estimate of that component will simply be 0. This is actually somewhat reasonable, as the tree will split along variables with small gradient components less frequently.
Of course, nothing would stop us from comparing values of means that are adjacent in the input domain but not adjacent in the tree structure (for example, nodes 3 and 6 of Figure 33. However, the advantage of considering only nodes adjacent in the tree is that this Brsed Gradient Estimator (TBGE) can be computed efficiently merely by traversing the tree. Furthermore, if we needed only an estimate of a gradient at a particular point x, we would need only to traverse the regression tree in the standard manner, visiting only nodes upstream of the leaf node x. To be explicit, if the tree is of depth K, recall that B (x) gives the index of the node of the greatest depth which contains x. We as our estimate of V fxx) the TBGE associated that node; that is, fx) B=
3.2 Integration
We next develop estimators for quantities of the form:
I(f) I(f== f ((T((N))))))
(4)
Here, f is some integrable R² + H. function and μ is measure on RR. The Integrated Gradient at point z with reference pointzz z" may be written in this form by choosing h(a) = (z (z-z) z Ca a, H = R P and μ as the degenerate uniform measure the line segment between and z.. Similarly, the Active
Subspace matrix can also be seen to belong to this class by setting h(a) = aa T H = R Px and arbitrary μ.
We will consider two classes of estimators for such quantities. The first a Monte Carlo Estimator (MCE) which is appropriate whenever y is probability measure which it is possible to sample
5

---

from. The second is Partition Basodd Estimator (PBE) which is suitable whenever we can compute u[aa, b)) for arbitrary a, b.
Start with the MCE. We fix some Monte Carlo sample size M and form the standard Monte Carlo approximation, then plug in the TBGE where the gradient appears:
I() ~
Σ (VV((x)) M
R
Σ Xm mM
h(Vs(xm)).
(5)
M
We denote this estimator by (f). particular, we can form free-Based Integrated Gradient (TBIG) as follows by sampling random uniform variables thm on [0, 1] and then forming:
M Σ 17
1 M
IG(x) = (x x')
Vf(umx + (1 )m))
(6)
Next, we consider the PBE. This involves simply computing weighted average of the action on the TBGE on each node at the penultimate depth K - 1, weighted by the measure of that node. For simplicity, we assume that 1( 1 In notation, we define the estimator as
irE(f)
E (G'))((T,'))
kENK-1
We this form Tree-Based Active Subspace (TBAS) for / as follows:
0 = E
G p(T u').
(8)
iENK
Which estimator is preferred in practice will depend on which properties of are computationally tractable. The ability to sample from μ makes the MCE tractable while the ability to compute the measure of an arbitrary rectangle makes the PBE tractable. If both are available, the PBE will be favorable it does not have Monte Carlo error.
4 Asymptotic Analysis
We'll now make rigorous the intuition developed in the previous section with a basic asymptotic analysis of the TBGE under simplifying assumptions. In particular, we assume that the split decisions are made on the basis of the feature variables only without reference to the outcome variables. Though this does not accommodate most algorithms used in practice for supervised learning. such as the the CART algorithm, these assumptions nevertheless are sufficient to develop some intuition as to qualitative properties of the approximation. Additionally, similar simplifying assumptions have often
been used in recent articles (e.g.Gaao et al. 2022, Ma et al. 2023) Cai et al. 2023 Wen and Hang 2022 Klusowski] 2021).
Theorem 4.1. Let S(N) denote the number of splits in the tree as a function of the sample size. Let 8 f(x), denote the TBGE at point x E 1). with sample size N. Under Assumptions 0, 1, and 2 of da,
the Appendix, we have that:
NN f(x)
0f(x) Oz,
2 P+2 S(N)
S(N) F
Op
+ P2
VN
In order for that error term to vanish, we need to choose S(N) growing even slower than log N, such P log log N (see Appendix for more discussion). This choice yields an error rate of the gradient estimates of (P(ooo N)-1), which is slow relative to typical estimation rates. This suggests that this gradient estimator may be most useful in situations where coarse estimate is acceptable. The reason that this rate needs to be so slow is that on the one hand, the number of datapoints in each cell needs to diverge order for the statistical error to vanish (given by the first term in the big O expression). But on the other hand, the Taylor series approximation error in the finite difference analog requires for the size of the cells to vanish (given by the second term), which implies an exploding number of cells. These factors combine to require a large number of data to achieve

---

small errors. However, they leave open the possibility of leveraging the computational efficiency of regression trees quickly create approximate gradient estimates in large samples, as our numerical experiments will show.
In the remainder of this section, will establish consistency of estimates for integro-differential quantities, which will require only consistency of the TBGE, which we have just established. We begin with the PBE; the remaining results are in the Appendix.
Theorem 4.2. Let h : R." + R." be bounded in the sense that h(z) S Cillzl| for an > 0. Under Assumptions 0, I and 2 of the appendix, the Partition Based estimator converges to the true integro-differential quantity as the sample size diverges. That is,
lim IPB(f) = I(f)).
N-020
where I(J) is the integro-differemtall quantity given in Equation
Theorem of the Appendix gives a similar result for the MCE. We also explicitly state there the implications of these results for Active Subspace and Integrated Gradient estimation, namely the consistency of the estimators C% and 1G proposed in Section
We have thus established consistency of gradient- model interpretation quantities for regression trees. Next, we will empirically study their behavior in finite samples via battery of numerical experiments.
Numerical Experiments
We now study how the proposed gradient estimator might be profitably exploited in practice. We begin with a qualitative study showing how a tree-based integrated gradient (TBIG) can facilitate local model interpretation. Then come three quantitative studies, first investigating the potential of a Tree-Based Active Subspace (TBAS) to improve prediction accuracy of a downstream tree via rotation of the space. Subsequently, we evaluate the capacity of regression trees estimate the Active Subspace in low and high dimension. Finally, we end with another qualitative study demonstrating how TBAS can provide data visualization.
5.1 Integrated Gradient for Tree-Based Methods
8'
7
Figure 4: Integrated Gradient for Trees. Each pair of panels gives a training example from MNIST. The second pair in the image superimposes the IG values onto the example. Redder means more strongly suggesting correct class membership.
We now consider a random forest classifier fit to two subsets of the MNIST dataset, one contrasting zeros against eights and the other fours against sevens. While classification was not the focus of this article, we present some preliminary numerical experiments in Appendix C.5 We use the estimator IG of Equation analysis. We see that when comparing eights against zeros, the intersection point of the eight is most important, while the left and right sides of the zero are. This makes sense they are the parts of each digit which are distinct. By contrast, the shared upper and lower arcs are not highlighted. In the four versus seven case, the location of the horizontal bar seems to be most influential in determining versus the other. This suggests that the model is comparing the relative position of the bar to the rest of the digit in making its classifications.
6 with M 500 random points along given path. Figure gives the results of this
5.2 Active-subspace Rotated Trees for Predictive Analysis
This section evaluates the ability of TBAS to improve the accuracy downstream predictive analysis. Given some mapping L, we refer to postmultiplication of the feature matrix X to form new
7

---

Dataset:
bike
concrete
gas
grid
keggu
kin40k
obesity
supercond
Regression
Tree (Depth
TBAS
0.635
0.47
0.578
0.688
0.194
0.856
0.128
0,511
Id
0.655
0.537
0.595
0.773
0.35
0.963
0.226
0.514
PCA
0.655
0.543
0.591
0.773
0.349
0.964
0.226
0.513
Rand
0.656
0.524
0.593
0.752
0.349
0.95
0.226
0.513
Regression Tree (Depth
TBAS
0.402
0.35
0.429
0.521
0.078
0.586
0.094
0.392
Id
0.405
0.403
0.432
0.522
0.121
0.862
0.103
0.395
PCA
0.407
0.395
0.423
0.524
0.122
0.872
0.107
0.392
Rand
0.411
0.391
0.435
0.55
0.124
0.836
0.109
0.397
Random Forest (Depth 4)
TBAS
0.609
0.406
0.559
0.602
0.161
0.802
0.123
0.479
Id
0.65
0.462
0,574
0.659
0.344
0.954
0.173
0.485
PCA
0.649
0.462
0,567
0.654
0.344
0.954
0.174
0.486
Rand
0.646
0.458
0.57
0.66
0.33
0.938
0.173
0.486
Table I: Predictive Impact of Various Transformations on Selected Datasets. Numbers give
100-fold RMSE; bold indicates confidence interval overlaps with the lowest confidence interval.
P=2
P=3
P=4
1.2
0.6
DASM
0.4
0.6
0.9
GP
0.8
PRA
10'4
10"
10'
10'4
10'
10'
10"
10a
Execution
Figure 5: Active Subspace Estimation in Low Dimension. Execution time (x-axis) and Subspace Estimation Error (y-axis) for the four methods, lower is better.
feature matrix Z XL rotation. In standard tree-based methods, non-diagonal rotations can have an impact on predictive performance because the axes along which splits are made have been changed. In order to quantitatively assess the utility of TBAS, regression trees and random forests on eight benchmark datasets fit on data augmented by a rotation of the space. A TBAS rotation is conducted by choosing L to be a matrix square root of the active subspace matrix estimate, following Wycoff et al. 2002). ). We compare TBAS rotations to the those made by drawing orthogonal directions uniformly (2001)) as well as those formed from a Principal Components Analysis (PCA; similar to Roodriuuz al. (2006)) and rotation all (denoted Id). Table Treseens the results of this analysis. TBAS does at least as well as the other methods, and sometimes offers significant improvement (such as on the Kin40k and Keggu datasets).
compare the prediction error of
the Grassmannian (Rand; similar to Breiman
5.3 Computationally Efficient Active Subspace Estimation in Low Dimension
In this section we demonstrate the capability of TBAS to offer extremely fast, gradient-fre estimation of the active subspace in low dimension when significant data are available. We compare the three popular methods for gradient-free active subspace estimation introduced in Section 2.2 based on a Gaussian Process (GP), Ridge Polynomial (PRA), and Neural Network (DASM), Each these methods was tasked to estimate one dimensional active subspace in dimensions 2, 3 and 4, using logarithmically spaced grid of sample sizes ranging from to 10,000 on a toy algebraic function. We found that the GP and PRA methods worked efficiently when sample sizes were small, but

---

Emor P=10
Error Pe
Error P=100
Time P=10
Time Pw50
Time P=100
Seconds
Up Seconds
Roders
Rodtard
DASM
10
10
10a
10"
107
107
10a
107
107
10'
107
107
10"
10"
102
10"
N
Figure 6: Sparse Active Subspace Estimation in High Dimension. Lower is better.
Spectrum
Data Projection
Prediction Projection
109
Relative Magnitude
Second Component
0.00
Second Component
0.00
6x
-0.25
-0.25
4x10-1
-0.50
-0.50
3x10
-0.75
-0.75
2x10-1
2
-0.5
0.0
0.5
1.0
Index
First Component
First Component
Figure 7: Projection with TBAS. Left: Spectrum of active subspace matrix suggests a 2D active subspace. Middle: Projection of data onto active subspace. Right: Projection of predictive surface.
computation time grew quickly, such that we were only able to run these methods for samples of size 150 less. F shows the active subspace error against the execution time. We that the tree-based estimator forms the majority of the Pareto front all three cases.
5.4 Estimating Sparse Active Subspaces in High Dimension
Imposing sparsity in the coefficients of linear dimension reduction can improve interpretability (Zou et al. 2006). Because of the manner that tree-based methods produce gradient estimates, we conjecture that TBAS has built-in inductive bias favor entry-wise active subspaces. this section, we will investigate this possibility by comparing TBAS against the DASM in estimating sparse active subspace in dimensions 10, 50 and 100. We will use the same setup as the previous section, except that the true subspace has only three nonzero coordinates. Because of the sample size that is required to estimate an active subspace high dimension, it is computationally infeasible to deploy the GP PRA active subspace estimation methods. Figure shows the results of this analysis. The TBAS estimator is able achieve much better accuracy with significantly smaller cost.
5.5 Dimension Reduction with the Active Subspace
We now turn to the qualitative benefits of performing active subspace analysis using TBAS. We used the NHEFS dataset biochemistry tape and mortality data which were studied by Lundberg al. 2019). This consisted of dataset of 14,407 observations and 90 complete variables. We fit a TBAS to this dataset using a regression tree of depth 15, requiring at least 10 samples per leaf. eigendecomposition of the estimated active subspace matrix. Like Lundherg et al. (2019), we found that age was the most important variable and it mapped cleanly onto the first active subspace dimension. However, we found that the next most important dimension consisted of many variables (see Appendix [.3).. such that they would have been difficult to capture with typical variable-importance analysis. Figure 7 shows the result of this active subspace analysis, which reveals that after the second eigenvalue there appears to be gap in the spectrum of the active subspace matrix, indicating the presence of active subspace dimension two (left panel). The middle panel shows projection of the data, which breaks into two clusters along the second principal component, while the right panel shows projection of randomly sampled points to visualize the predictive surface of the function. The right panel reveals the predictive surface has a fairly simple, "S-shaped" form over these two dimension. It would not possible to detect this by considering only main effects two factor interactions.
We subsequently performed

---

Discussion
Summary: We studied a simple method for estimating gradients in sufficiently deep regression trees on large datasets. Subsequently, demonstrate how these estimates could be used to calculate active subspaces and integrated gradients. We found significant improvement in predictive performance could be achieved by using the tree-based active subspace to rotate the space, and also found that these estimates executed quicker than existing gradient-free active subspace estimators and had useful inductive bias towards detecting coordinate-sparse subspaces. Finally, we used these gradient estimates to reveal the simple global structure of a tree-based model fit to a complex dataset as well as the mechanism by which a random forest conducted MNIST classification.
When it comes to limitations of our experiments, when comparing our active subspace estimates to the DASM, we used particular neural network architecture and optimizer. It is possible that a different configuration would have performed better. Additionally, when it comes to limitations of the method we studied, our analysis suggests that it would take a very deep regression tree to estimate gradients to high accuracy in high dimension.
Limitations:
Conclusions: We think this work offers two high level conclusions. First, that trees may have place in the field of Uncertainty Quantification, which has more commonly used differentiable but slow to estimate surrogates such as Gaussian processes and neural networks. Secondly, we hope that this work can also enable improve cross- polsssoolinntion between developments in interpretability for neural networks and for regression trees by creating analogs for gradient-basce bbased neural network techniques.
We also would like to comment on how TBAS fit into the existing literature on interpretability in trees. It is somewhat distinct from the axiomatic approach to interpretabilitt proffered by SHAP (Lundberg and Lee, 2017) and Integrated Gradients (Sundararajan al., 2017). While an axiomatic approach can be useful, its universality should not be exaggerated. Hancox- Li and Kumar (2021) write about how it is unlikely that any variable selection method could satisfy all possible demands, no matter how attractive its axiomatic foundation. Since the active subspace is parameterized by measure, it actually consists of an entire family of analyses, with different choices of emphasis over the input space possibly leading to different conclusions.
Future Work: We are excited about the future work opened up by the here-proposee gradient estimates, First, we suspect that part of the reason for the slow convergence rate of the gradient estimator is that we "start from seratch" at every depth of the tree, overwriting the previous estimator. Perhaps an improved convergence rate could be obtained by combining the gradient estimate from multiple depths rather than overwriting it. Next, while we have conducted some preliminary analyses in Appendix C.5] more work is needed to understand the properties of these estimates in classification problems with categorical inputs and missing data. We are also interested in the possibility of estimating higher order derivatives from tree structure. Furthermore, extending the class of functions approximated to nondiffcrentiable functions is of interest: does the quantity proposed here converge in such case, and to what? But are most excited about the potential to bring in other rradient-based techniques to tree-based methods. For instance, physics-informe (2019 2017)) has been making waves in the fluid dynamics community (Cai et al. 202T) among other applications, where they allow the analyst to use information about function derivatives to improve predictions of differentiable models such neural networks or Gaussian processes. Our gradient estimator opens up the possibility of deploying this technique in the context of regression trees.
machine learning (e.g. Raissi et al.)
Acknowledgments and Disclosure of Funding
I gratefully acknowledge funding from the NSF and NGA via DMS#2428033 as well as the NSF and AFOSR via DMS#25592777. The computational resources for this work were provided by the Unity Research Computing Platform, a multi-institutional cluster lead by University of Massachusetts Amherst, the University of Rhode Island, and University Massachusetts Dartmouth. This project was inspired by discussions at the 2024 AISTATS conference.
References
Antoniadis, A., Lacbert-L S., and Poggi, J.-M. (2021). Random forests for global sensitivity analysis: A selective review. Reliability Engineering & System Safety, 207:1.
10

---

Bradbury, J., Frostig, R., Hawkins, P., Johnson, M. J., Leary, C.. Maclaurin, D., Necula, G., Paszke, A., VanderPlas, J., Wanderman-Miine S., and Zhang, Q. (2018). JAX: composable transformations of Python+NumPy programs.
Breiman, L. (2001). Random forests. Machine learning. 45:5-32.
Breiman, L. (2002). Manual on setting up. using, and understanding random forests v3. 1. Statistics Department University of Califormia Berkeley, CA, USA, 1(58):3-42.
Breiman, (2017). Classification and regression trees. Routledge.
Cai, S., Mao, Z., Wang, Z., Yin, M., and Karniadakis, E. (2021). Physics-informed neural networks (pinns) for fluid mechanics: A review. Acta Mechanica Sinica, 37(12):1727-1738
Cai, Y., Ma, Y., Dong, Y., and Yang, H. (2023). Extrapolated random tree for regression. In International Conference on Machine Learning, pages 3442-3468. PMLR.
Chaudhuri, P., Lo, W.-D., Loh, W.-Y., and Yang, C.-C. (1995). Generalized regression trees. Statistica Sinica, pages 641-666.
Chen, H., Janizek, J. D., Lundberg, S., and Lee, S.-L. (2020). True to the model or true to the data? arXiv preprint arXiv:2006.166 16234.
Constantine, G. (2015). Active subspaces: Emerging ideas for dimension reduction in parameter studies. SIAM.
Edeling, W. (2023). On the deep active-subspace method. SIAM/ASA Journal on Uncertainty Quantification, 11(1):62-90.
Elie-Dit-Cosaque K. and Heuume-eschamps, V. (2024). Random forest based quantile-oriented sensitivity analysis indices estimation. Computational Statistics, 3944):174711777.
Friedman, H. (2001). Greedy function approximation: a gradient boosting machine. Annals of statistics, pages 1189-1232.
Gao, W., Xu, F., and Zhou, Z.-H. (2022). Towards convergence rate analysis of random forests for classification. Artificial Intelligence, 313:103788.
Hancox-Li, L. and Kumar, I. E. (2021). Epistemic values in feature importance methods: Lessons from feminist epistemology. In proceedings of the 2021 ACM conference on fairness, accountability, and transparency, pages 317.
Hechtlinger, Y. (2016). Interpretation of prediction models using the input gradient. arXiv preprint
Hokanson, J. M. and Constantine, P. G. (2018). Data-driven polynomial ridge approximation using variable projection. SIAM Journal on Scientific Computing, (156))11566-1115
Hooker, G., Mentch, L., and Zhou, S. (2021). Unrestricted permutation forces extrapolation: variable importance requires at least more model, or there is no free variable importance. Statistics and Computing, 31:1-16.
Ishwaran, H. (2007). Variable importance in binary regression trees and forests.
Karezmarz, A., Michalak, T., Mukherjee, A., Sankowski, P., and Wygocki, P. (2022). Improved feature importance computation for tree models based the banzhaf value. In Uncertainty in Artificial Intelligence, pages 969-979. PMLR.
Kazemitabar, J., Amini, A., Bloniarz, A., and Talwalkar, A. S. (2017), Variable importance using decision trees. Advances in neural information processing systems, 30.
Klusowski, J. (2021). Sharp analysis of simple model for random forests. In International Conference on Artificial Intelligence and Statistics, pages 757-765. PMLR.
Klusowski, J. M. and Tian, M. (2020). Nonparametric variable screening with optimal decision stumps. arXiv preprint ar Xiv: 2011:2001..0283

---

Li, X., Wang, Y., Basu, S., Kumbier, K., and Yu, B. (2019). A debiased mdi feature importance measure for random forests. Advances in Neural Information Processing Systems, 32.
Loh, W. (2011). Classification and regression trees, Wiley interdisciplinary reviews: data mining and knowledge discovery, 1(1):14-23. 23.
Louppe, G. (2014).
Understanding random forests: From theory practice. arXiv preprint
Lundberg, S. M., Erion, G., Chen, H., DeGrave, A., Prutkin, J. M., Nair, B., Katz, R., Himmelfarb, J., Bansal, N., and Lee, S.-I. (2019). Explainable ai for trees: From local explanations to global understanding. arXiv preprint 1905:19050046100
Lundberg, S. M. and Lee, S.-I. (2017). A unified approach to interpreting model predictions. Advances in neural information processing systems, 30.
Ma, Y., Zhang, H., Cai, Y., and Yang. H. (2023). Decision tree for locally private estimation with public data, Advances in Neural Information Processing Systems, 36:43676-43705
McCloskey, K., Taly, A., Monti, F., Brenner, M. P., and Colwell, L. J. (2019). Using attribution to decode binding mechanism in neural network models for chemistry. Proceedings of the National Academy of Sciences, 1 116(24): 1624-11629
Pedregosa, F,, Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesmay, E. (201 1). Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830.
Raissi, M., Perdikaris, P., and Karniadakis, G. E. (2017). Machine learning of linear differential equations using gaussian processes, Journal of Computational Physics, 348:683-693.
Raissi, M., Wang, Z., Triantafyllou, M. S., and Karniadakis, G.E. E. (2019). Deep learning of vortex- induced vibrations. Journal of Fluid Mechanics, 861:119-137.
Rodriguez, J., Kuncheva, L. I., and Alonso, C. J. (2006). Rotation forest: A new classifier ensemble method. IEEE transactions on pattern analysis and machine intelligence, 18110):661-11600
Sandri, M. and Zuccolotto, (2008). A bias correction algorithm for the gini variable importance measure in classification trees. Journal of Computational and Graphical Statistics, 17(3):611-628.
Sayres, R., Taly, A., Rahimy, E., Blumer, K., Coz, D., Hammel, N., Krause, J., Narayanaswamy, A., Rastegar, Z., Wu, D., et al. (2019). Using a deep learning algorithm and integrated gradients explanation to assist grading for diabetic retinopathy. Ophthalmology, 126(4):552-664
Shan, H., Zhang, J., and Kruger, U. (2015). Learning linear representation of space partitioning trees based on unsupervised kernel dimension reduction. IEEE Transuctions Cybernetics, 46(12):3427-3438
Strobl, C., Boulesteix, A.-L., Kneib, T., Augustin, T., and Zeileis, A. (2008). Conditional variable importance for random forests. BMC bioinformatics, 9:1-11.
Strobl, C., Boulesteix, A.-L., Zeileis, A., and Hothorn, T. (2007). Bias in random forest variable importance measures: Illustrations, sources and solution. BMC bioinformatics, 8:1-21.
Sundararajan, M., Taly, A., and Yan, Q. (2017). Axiomatic attribution for deep networks. In International conference on machine learning, pages 3319-3328. PMLR.
Tripathy, R. and Bilionis, I. (2019). Deep active subspaces: A scalable method for high-dimensional uncertainty propagation. In International Design Engineering Technical Conferences and Comput- ers and Information in Engineering Conference, volume 59179, page V0017024074, American Society of Mechanical Engineers.
Vannucci, G., Siciliano, R., and Saltelli, A. (2024). Enhancing variable importance in random forests: A novel application of global sensitivity analysis. arXiv preprint 4rXiv:2407.14194
12

---

Wen, H. and Hang, H. (2022). Random forest density estimation. In International Conference on Machine Learning, pages 23701-23722, PMLR.
Wycoff, N., Binois, M., and Gramacy, B. (2022). Sensitivity prewarping for local surrogate modeling. Technometrics, 64(4):535-547.
Wycoff, N., Binois, M., and Wild, S. M. (2021). Sequential learning of active subspaces. Journal of Computational and Graphical Staristics, 30(4):1224-1237.
Zou, H., Hastie, T., and Tibshirani, R. (2006). Sparse principal component analysis. Journal of computational and graphical statistics, 15(2):265-286.
13

---

A Proofs
We begin by stating and discussing our assumptions.
major difficulty in establishing theoretical results for tree-based methods establishing the behavior of the thresholds as function of the data generating process. For purposes, the critical assumption that the volume of the leaves shrink at an exponential rate the number of splits made. We will study scheme which achieves this by cycling between variables to split along at each depth, and subsequently splitting at the median of datapoints in each node along the split variable, such that about half of the data in the current node lie in each child node. To illustrate, the first split in the root node is made on variable 1, then at depth two, both child nodes have about half the data and themselves split along variable 2, and subsequently the four child nodes, each with fourth of the data, split along variable 3. When we reach depth of P + 1, the 2 splits will again be along variable and each node has about 2 many points in
This is of course typically not be how a regression tree is fit in the supervised setting, which will typically calculate splits taking y values into account. Establishing the convergence rate of the TBGE in such settings is left as future work. We believe that even the present proof, provided in the simplified setting, nevertheless provides valuable intuition the advantages and limitations of the TBGE.
Our first assumption concerns the splitting rate. Assumption 0. Let S(N) denote the depth as a function of sample size.
1. lim S(N) oC. N-+oc
2. lim S(N) N log N
0.
This very slow rate of splitting is necessary to ensure that the number of datapoints in each node can grow to infinity while still eventually achieving arbitrarily small nodes.
Our next assumption is on the process which generates the feature variables. Assumption 1. The input points x, sampled from distribution such that for any 0, there are constants C_, C+ > 0 and some Ne such that for all N >> No. we have:
P CC_2 D2 S u
Ap E (I....,P).
where D, 1= (1 + 1)] is the depth of node
This assumption tells that the width of the leaf nodes will shrink exponentially. This assumption is most likely to be violated in observational contexts, where the feature variables may live on some manifold within [0, 1] and thus leave gaps within the unit cube unfilled. Naturally, the gradient estimates for regions without data will not behave well. However, this assumption may be satisfied in contexts where the feature variables may be set by the experimenter. In particular, this property holds for the uniform distribution, as we now discuss.
Remark 1. Assumption is satisfied if x XN iidd U(O 11 and S(N) = [logz log2 NJ.
Start with the case P = 1, where we have uniform data on [0, 1). and are making S (N) many recursive splits so as to keep an equal number of points in each bin. The distribution of the bin borders is given by the order statistic distributions. For uniform data, it is known that the difference between the 7th and thth order statistics is given by a Beta distribution with a = k j and 3 + (k (k-j) j) when le > j. each bin has 20(1 observations, l bin width is thus:
Proof.
29(1j and the marginal distribution of
N 25(N)
N
u' 1' ~ Beta
N +1
28(N)
We thus have that:
Eluu - 19]
N+1
25(NT
14

---

2. Vlu' [2]
(N+1)+(N42) (IN=I
N2 (1 2
M N290NT
2
where M [N+1)*(++2)
क ) which is bounded above by for all N 2 1.
We next develop a Chebyshev bound, valid for all & > 1:
N
kM N2S(N)
P (u' - 14) N+1 25(N)
S
2
R.2
= P (lastMna -1)
N
2S(N)
I kM
2 1
N +1
N
1-2
We now fix some O, and set k -/ such that:
2s - -1)) N +
N
2S(N) 1
S
M
2
21-E
N
Ve
>(((2Ssi(w 12)
N
2S(N)
21-6;
+
N
Ve
where in moving between the lines we have dropped the M term as M S This gives us that, with high probability,
25(N) (u - 1) - N N+1
N
2S(N)
Ne
25(N)
N
25(N)
I 2
(u 1) N +
I Ne
Ne
2S(N)
N
/2S(N)
N
228(N
(u 1) $
Ne
N +1
Nc
N +
N
2S(N)
N
25(N)
2 S(N)
S (u - 1) 2 S(N)
+
N +1
Ne
N +
Ne
The quantity
28(N) N 1l at N and N+I
(N))(N)
viewed as a continuous function of N, achieves its maximum value of is bounded above by therefore:
N²
2 S(N(
N
2S(N)
2-N)(N)
2 S(N)
(1+
1+
1
Ne
log(2)e
Using the fact that S(N) yields:
N N+I
is bounded below by 1/ for N 2 and plugging in the bound expression for
N
2S(N)
(ogg((N)
2 S(N(N)
2 2- S(N)
2-N(
N N+1
Ne
Ne
Choosing N large enough that
log N
- will ensure that 1
log,(N) Ne
L is positive.
We thus arrive at the following with high probability:
S(N) s u - 2 S(N) 1
log (2)e
When 1, we alternate between splitting along each variable. The marginal distribution of up remains uniform within each split node, which allows to reduce the general dimensional case to the one dimensional case. However, each variable split only every pth pass, which rescales the S(N) term in the exponent by $.
15

---

Our final assumptions are on the function and error process.
Assumption 2. Let Vn = f(x,) En. We assume that:
1. The estimate of the mean of (xx over some interval [a, b] converges at the usual square root rate; this is achieved for example if the error terms Ci...,,En EN such that E(e,, = 0:
V [(e) S 0o and cn, 1L. 6ng Vun, 112 E (1,...,N).
2. f is twice differentiable with [x](()) & H Vx E [0, i.e. I has a Hessian with operator norm bounded by H.
The first assumption gives that the sample means in given node converge to the integral of the function over that node normalized by the node's volume. The second assumption allows us to bound the error of 1st order Taylor approximation.
We are now prepared to prove our results.
Theorem 4.1. Let ((N) denote the number of splits in the tree as a function of the sample size. Let 8 f(x) denote the TBGE at paint 10 with sample size N. Under Assumptions 1, and 2:
82,
JN f(x) dzp
0f(x) dzp
2
2
P+2
800
+Op
+ P2
VN
Proof. At each node i, the quantity "/ serves as our estimate the partial derivative in the o; direction that node. For a fixed i, do not expect convergence of 7/2 to any gradient quantity. However, we do expect convergence as we go down the tree depth for suitably chosen S(N).
We wish to estimate the partial derivative at some location x E [0, 1] given sample of size N. According to our simplified splitting scheme which alternates between variables, and given the depth (NN) P, the most recent split along variable is given by the deepest node of depth K no greater than ((N) which splits along variable p (that is, p (mod P)) and which contains x (that is, 8 (x) i). Our task is to show that this sequence of y. with i thusly viewed implicitly function of N, will converge (f(x)
Stp
Recall the definition of the diffeeeifference like estimate:
2(pt pi)
7/4
U 13
and a; = p by our choice of
At is the mean of the data falling within the left child of node Assumption 2.1 gives that within any rectangle, the sample mean converges to the population mean at the usual square root rate as function of the number of points in that rectangle. In the case of the simplified splitting scheme, the number of points a cell is given by the total number points divided by the number cells, or Hence have that:
N by 25(55.
25(N) N
(V 2S(N)
A1
E X-U (1I
[f(x)] + Op
= Hi +i +0
(10)
N
where the second equation serves to give our definition of p/. a quantity independent of our dataset and instead dependent f. the mean function of the relationship being approximated. Here, the expectation is taken with respect to the uniform distribution over the bounds of the left child node of which before denote by et. We of course have similar definition for the right child node's mean pi..
Next we approximate f at an arbitrary point z [I u') by expanding it about (or any other point in [T wf). using the Lagrange form of the remainder with & dependent on z:
f(z) f(x) + V (z x) - (z x) TV2 - x))
(11)
16

---

and plug this into the definition of ja;:
22 [f(x) + Vf(x)* (z-x) xxx)++ 1 2222 x) ( (²)((((( -x]]
1
E -- (r(
x)]
=f(x) + 1 [V(()T + (ri+ VS(() x
(a-x) V())) x)]
2~ (rt
We needed only the linearity of expectation to evaluate the first two terms. Since we likewise have:
μ f(x) + 1 T(()) (r+ + u vf(x)
E
(z-x) T (2f(E)(2 x)].
2 2~ (e0((1tu
taking the difference yields:
, - ni = vf(x)* (r+ l urt u²) + R.
where
E R x- (net,
[(2 x) T 22 (({(x)(2 --1x-xxx))
1
E
[[z x) x) V f(((x))) x)].
2 2~ (1
As siblings, the bounds of c². and of agree except for along the p dimension, such that:
(1s vx(x)
1 n u
Σ 0f(x) (1/ 1/ + ut utt) +
Of(x)
(7' - 1/ + ur -²) = 0f(x)
Ozp (u -1))
dxp
kpp
Therefore:
10f(x)
14 14
(u² - R,
2 dz.
such that
2(14 - 14)
0f(x)
2R
u/p 19 dx,
up
Let's now work to develop R. Note that:
E ust)
[(a x) T (({)))) -x]] x)] 5 max
(z- x) (V(((()))==) (12)
C.S. max 2c(
|1-11
|z - x V2 (((()))) - x)]1
||- { (13)
max 2E [
The first inequality comes from the absolute integral being less than the max of the absolute integrand, the second comes from Cauchy-Schwand Bounding the max of the produet of positive quantities by the product of the maxes and invoking our bound on V [((())) will be our next steps, yielding:
and the third from the definition of the operator norm.
max 2E(
Iz
x
(()((())) s H I|u 1'12
Making similar moves for the left child node gives that:
2|
2 2| 12112
<
H
11
17

---

Under assumptions the splitting process, have that C_ S0M
< 104
- S 2-
for some C-, C+ > 0 with high probability. Thus, also with high probability:
lu' 11 4
PC
2
C² P
S(N)
2
"
C-2
P
C
and therefore
2
14) P
0s(x) Oxp
800
+ +Op
P2
15
We thus have a bound on the difference between the functional mean and the gradient, but have thus far been ignoring error in the estimation of these means. To bring this into the equation, we begin by noting that, with high probability:
(V 2S(N) N
SSN))) N
P.
ir - 14 + Op
+ Op
11
up
This is because for large enough N, u which gives us that:
12 2 C_2
S(ND
with high probability. and similarly for pit-
2 A1)
2( mi)
2 21 S(N)
Op
" 1 " 12
VN
Combining with earlier work yields:
2 11)
0f(x)
2 2 S(N)
S(N) + P2
+ +Op
P
a 1/2 Oxp
Now let S(N) = P log log N. Then:
2 Pr S(N)
(2g log log N) 1+
(log N) +1
P log N
P2
+ P2 loglog N
VN
VN
VN
Since the first term vanishes relative to the second, we obtain:
2(p A u 1 dz,
0f(x)
+ Op
log N
Theorem 4.2. Let h: P + P be bounded in the sense that hu(z) S Cn Illl for on > O. Under Assumptions O, and the Cartition-Basel estimator converges to the true integroddifferentall quantity as the observation sample size diverges. That is,
lim Irp(S) lim Σ ((" u')) = - I(J). Noc
N-+00 VENx-1
Proof. Since the function sequence (x) = G B+ (x) converges pointwise to V f by Proposi- tion 1, we need only establish function (x) which dominates gx(x) and apply the Dominated Convergence Theorem.
To this end, denote by C", Cdl the child nodes of node and examine its gradient estimator's pth entry, given by:
2( Wor SNer f(x)dx Woyl INC. fx))xx)
2(1 - v4) N0000 u/ p
(14)
ub 13
18

---

The magnitude of this difference in averages is bounded by the magnitude of the difference of extremes:
Worl NoT J f(x)dx
/
[Wey]
No.
f(x) <
max (x: c2 xN
-
f (15)
But since is continuously differentiable, it also Lipschitz continuous (call the constant L), and we have that:
max (x1,2))ENor xNaf
15(x1) - [(x2)] S T||x1 X2l12 S PT][X1 X2|120
(16)
Therefore:
2(UC - vcti) u$ 1
|(PL]|xx - -2 S 2PL.
-
(17)
Hence (x))22) 2P and thence C₁ (2P22 L bounds (xx).. Since the integral is over
the unit hypercube, the constant function is integrable and we can apply the Dominated Convergence Theorem to yield the desired result.
Theorem A.1. Under Assumptions 1 and 2, the Monte Carlo estimator converges the true integro- differential quantity as the Monte Carlo sample size and the observation sample size diverge. That is,
lim Imo(J) N,
= lim N,M-X M
E (() I(I) Mm
Proof. This follows from the fact that
lim lim
M Σn ((((xm))
(18)
N -00
Xm rup
lim N x
h(V((x)ddp=
= lim Σ (GG)) N-00 RED
(19)
and application of Theorem 4.2.
A.1 Implications for Active Subspaces and Integrated Gradients
We conclude this section by explicitly stating the implications of these results for Tree-based Active Subspace (TBAS) estimation.
Corollary A.2. Let KNN) denote the depth of the regression tree as a function of N. Under Assumptions I and 2, we have that
lim N
Σ
G.G.
four (x(x)V/(x)dp(())
(EDR(N)11
Proof. Follows from Theorem 4.2
As well for Tree-Based Integrated Gradient (TBIG) estimation.
Corollary A.3. Let K(N) denote the depth of the regression tree as a function of N. Under Assumptions I and have that, assuming that un iid uniform [0,1]:
1 Σ
lim K.N.
(x xx-xx)0
vf (um x + Um )xm)
= (x - x*) o
Vf(ax + (1 (1- -oxx)")ds
a==
19

---

Tree Depth 4
bike
concrete
gas
grid
0.8
1.0
0.7
8
0.8
0.6
0.5
TBAS
TBAS
Rand
keggu
kin40k
obesity
supercond
о
0,6
0.2
0.5
0.8
0.0
PCA
TBAS
TBAS
Rand
TBAS
Rand
Tree Depth 8
bike
concrete
gas
grid
1000
0.7
0.5
0.6
0.5
I
0.5
PCA
TBAS
Rand
keggu
kin40k
obesity
supercond
0.2
0.8
0.2
T
T
0.4
0.0
0.3
PCA
TBAS
TBAS
Rand
TBAS
Rand
Random Forest Depth 4
concrete
gas
grid
0.7
0.75
0.7
0.7
0.6
0.50
0.6
0.5
0.5
TBA5
Id
PCA
Rand
T8AS
1d
PCA
Rand
TBAS
Id
PCA
Rand
TBAS
PCA
Rand
keggu
kin40k
obesity
supercond
0.4
0
-
I
T
O
0
Q
0.2
0.5
T
0.2
0.8
0.1
I
0.4
Figure 8: Boxplots corresponding to Table
Proof. Follows from Theorem A.1
B Details of Numerical Experiments
This section gives additional details and discussion of the numerical results presented in Section S All tree-based models are estimated using Scikit-Learn Pedregosa et (201I)
B.1 Rotation Prediction Study Additional Details
In this study, when performing rotation, used only the /P many PCA components or Active Subspace dimensions, and appended these original design matrix as new variables. We measure prediction error using 100-fold cross validation.
20

---

The table below gives the parameters of the datasets used for the prediction study of Section 3.2
Name
N
URI.
concrete
1,030
9
uci
kin40k
40,000
9
py
keggu
65,554
28
httpp::/wwwe / httpe//wwnnn..ee//g///aaaaaaaaaa
bike
17,379
https://archive.ic.. ics. http://cciieeeeeeeucceeeeaaaaaas
obesity
2,111
24
gas
36,733
12
grid 10,000
attpa://archire http:/cc......aaattaataatt/////a
supercond
21,263
nttps://archive.1 wtw..//........c/ddaaaaattt///
We also provide boxplots of Cross Validation errors in Figure Running this study took about five hours on a 40 core Ubuntu machine with 128 GB of RAM.
B.2 Active Subspace Estimation Study Additional Details
In Section 5.3 We randomly sampled a unit vector from the uniform distribution over directions and then sampled input points uniformly at random on the unit cube. We subsequently evaluated the function [x) cos(6r(a (x 0.5)) which was treated as the noiseless observed response y. We compared the estimates with using the angle each made with a. This experiment was repeated 20 times.
We used the implementation of PRA provided with the pypi package PSDR For GP-based active subspace estimation, we used the CRAN package activegp. We used all default settings for the PRA method as well as for the GP method. For the DASM, we used neural network with an additional layer of width 512 subsequent to the active subspace layer, and used gradient descent with step size of 10-3 on the Mean Squared Error cost function. This neural network was implemented JAX Bradbury et al. (018). In addition to the quantitative advantages enjoyed by the tree-based method of active subspace estimation, we would also like to note that like the GP-based method, and unlike the PRA and DASM, it provides estimate of the entire active subspace matrix, rather than simply a basis for the active subspace. This is important for two reasons. First, with the active subspace matrix in hand, subspace is most desirable, or to get some idea of how much information is being lost in, say, a two dimensional visualization. And secondly, it allows having seen the data rather than before, without requiring the estimation procedure to be re-run.
create analogs of PCA scree plots to determine what dimension of the active
decide
active subspace dimension after
Running this study took about eight hours on a 40 core Ubuntu machine with 128 GB of RAM.
B.3 NHEFS Data Analysis Details
This table presents the first eigenvectors of the mortality data analysis, restricting to the top 9 variables with highest coefficients. The first eigenvector captures almost entirely the age variable, which Lundheer et al. (2019) also found to be most important. We see that the second eigenvector is evenly distributed across sex and one of the urine variables. The third eigenvector is dominated by the urineDark variable.
Eigenvector
age
wrineDark
urineNeg
SGOT
hemoglobin
urineAlb
total
physical
-1.00
-0.00
0.01
0.01
-0.00
-0.00
0.00
-0.00
-0.00
2
0.01
-0.15
0.56
0.53
-0.28
-0.30
0.30
-0.16
0.09
3
-0.00
-0.96
-0.03
-0.11
0.16
0.07
0.02
0.04
0.07
When producing the right panel of Figure 7 used the prediction after accounting for the effect of age in order demonstrate the change in the predictive surface over the second and third eigenvalues.
21

---

Density=0.25; Depth=4.0
Density=0.25; Depth=124
10
1.20
10
1.20
1.05
1.05
8
0.90
8
0.90
0.75
0.75
6
0.60
0.60
0.45
0.45
4-
0.30
4
0.30
0.15
0.15
2
0.00
2
0.00
2
3
5
Log Sample Size
Log Sample Size
Density=1.0; Depth=4.0
Density=1.0; Depth=12.0
10
1.28
10
1.4
1.20
1.2
8
1.12
8
1.0
1.04
0.96
6
6
0.88
0.6
4
0.72
0.80
4
0.4
0.64
2
0.56
2
0.0
Log Sample Size
Log Sample Size
Figure 9: Convergence Gradient Estimates in Sample Size.
C Additional Numerical Experiments
C.1 Empirical Gradient Estimate Quality
We present the results of simulation showing the empirical performance of TBGE in estimating gradients under various tree depth, sample sizes, dimensions and gradient densities on the function [(x) = log(1 + a x) with nonzero elements of generated from iid Gaussian. Figure 9 contains heatmaps showing the results for all combinations of a 25% and 100% dense gradient and a depth and 12 tree. In each figure, the x-axis gives the sample size and the y-axis the problem dimension. The color represents the angle between the true and estimated gradient. We see that deep tree is able decrease error as sample size increases while shallow one cannot, and also that error decreases much faster for the sparse gradient.
C.2 Gradient Error Comparison against GP Surrogate.
In this section conduct study similar Section 5.3 but focus directly the gradient quality rather than the active subspace quality. That is, we compare the accuracy of gradient estimates produced by regression tree against those provided by Gaussian process for fixed compute time, rather than fixed dataset size. The idea is that on simpler simulations, we may be able to produce an abundance data and that trees might be useful this scenario. In Figure [0, find that indeed the tree can produce useful estimates extremely quickly for larger sample sizes, leading to some comparative advantage compared GP fit smaller sample size (but taking even longer make predictions).
C.3 Active Subspace Estimation Performance under Noise
This section repeats the experiments of Section 5.3 where the output data contaminated under small i.i.d. Gaussian noise with standard deviation 0.1. The results, presented in Figure 11 are very similar the noiseless case but nevertheless included for completeness.
C.4 Gradient Estimate under Input Variable Correlation
Our numerical experiments on real data suggest our proposed method can operate under correlated inputs, and in this section conduct an experiment to more closely investigate quantitatively the
22

---

levy
CO5
ackley
1.4
Gradient f, Enor
Gradient Error
Gradlent Error
Forest
1.0
0.6
1.0
GP
0.4
Forest
Forest
0.2
0.8
10-2
10-1
10-2
10
10-2
10-1
Time
Time
Time
Figure 10: Gradient Error Comparison against GP surrogate.
P=2
Pw3
(Radians)
0.6
0.9
0.6
0.8
0.4
PRA
0.6
TBAS
0.2
0.5
0.0
000
10 Execution Time (s)
10t1
10-1
10'
10"1
10¹
Execution Time (s)
Execution Time (s)
Figure 11: Active Subspace Estimation with Gaussian Noise (std=0.1;iid)
impact of input-variable correlation on gradient estimate quality. Sampling data from truncated normal in 5D with correlation varying from 0 to 0.99, evaluated estimates of the Ackley function's gradient at 100 random points. The results are presented in Figure [2 We see that correlation can have some deleterious effects on the gradient estimates; however, it requires very high level of correlation before the estimates are significantly affected.
C.5 Numerical Experiments on Classification Trees
We repeat the experiments of Section 5.2 but now by replacing each regression problem with classification problem by assessing whether a given observation falls above or below the median observation. The results are given Figure Intriguingly, the results are significantly less
Error vs Sample Size and Correlation
1.2
1.1
f: Gradient Error
1.0
0.9
0=0.0
0=9
0.8
0.95
10a
10
10*
N
Figure 12: The Effect of Correlation on Gradient Estimates.
23

---

Tree Depth 4
bike
concrete
gas
grid
0.5
8
8
88
0.6
0.4
0.5
0.45
0.5
0.40
0.4
0.3
0.0
0.35
PCA
TB4S
PCA
keggu
kin40k
obesity
supercond
0.25
--
6
I
0.4
0.20
I
I
0.15
0.5
TBAS
Rand
TEAS
PCA
PCA
TBAS
PCA
Rand
Tree Depth 8
bike
concrete
gas
grid
0.4
T
0.50
0.4
0.5
0.3
0.4
0.3
0.3
0.00
Bard
keggu
kin40k
obesity
supercond
0.6
0.3
0.1
0.5
5
0.2
0.0
0.0
Rand
Rand
TB46
FCA
Fand
Random Forest Depth 4
concrete
gas
grid
0.45
0.5
0.5
0.4
0.3
0.0
0.35
0.3
0
TBAS
Id
PCA
Rand
TAAS
1d
PCA
Rand
TBAS
1d
FCA
Rand
TBAS
PCA
Rand
keggu
kin40k
obesity
supercond
0.3
0.4
0.6
9
0.4
0.2
0.2
I
0.3
0.5
0.0
0.2
Figure 13: Classification Exercise: Brier Scores are indicated; lower is better.
promising for the TBAS method, despite the fact that by construction, there is structure in the data that TBAS could possibly exploit. This indicates that there may be special considerations to be taken in deploying this methodology to classification problems.
24

---

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: We propose new way to get gradient information from regression trees, as we mention in the introduction.
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
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 to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Yes we have a dedicated Limitations section in the discussion.
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 a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In 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 approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
25

---

Justification:
We provide all proofs in the supplementary material, and carefully list our assumptions as part of Assumption and Assumption 2 of the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented 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
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide all necessary details to reproduce our paper the narrative and algorithms.
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 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 novel architecture, describing the architecture fully might suffice, or if 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 is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome 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 possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
26

---

reproducible, they Question: 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?
Answer: [Yes]
Justification: We provide code reproducing our results and a README with instructions for doing so.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttps://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/
/ooeee/e//ooSSSomiaiio ssi onPolicy) 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 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 is 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: We provide all necessary information when describing our runs.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: In our numerical results we use confidence interval overlap to assess signifi- cance.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
27

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror 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:
We provide this in Appendix B.2.
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 or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
Yes we respect this code of ethics.
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 in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
Yes we give discussion of this in the Discussion section.
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 not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
28

---

The conference expects that many papers will be foundational research and not tied 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 negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
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:
This work has a low risk of misuse.
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 requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses 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: We give dataset information in Appendix B.I.
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 (c.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 package should be provided. For popular datasets, papprswiiiiii theode com datastts has curated licenses for some datasets. Their licensing guide can help determine the license 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.
29

---

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 documentation provided alongside the assets?
Answer: [NA]
Justification: This paper primarily introduces methodology.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel 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 paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing or other human subjects whatsoever.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No crowdsourcing or other human subjects whatsoever.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
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 the institution conducting the review.
16. Declaration of LLM usage
30

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods 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.
Answer: [NA]
Justification: LLMs were not involved in any aspect of this project.
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.
31


Reviews:
[{"review_id": "bmTYFvvWTR", "reviewer": "Reviewer_oJvh", "summary": "This paper introduces a method for estimating gradients from regression trees by computing finite differences between adjacent nodes in the tree structure. The authors propose using these gradient estimates to enable gradient-based interpretability techniques for tree models, specifically focusing on Active Subspace methods and Integrated Gradients. The key insight is that the difference in mean responses between left and right splits, normalized by node width, approximates partial derivatives. The paper demonstrates applications including tree-based active subspace estimation (TBAS), tree-based integrated gradients (TBIG), and shows these can improve predictive performance and provide model interpretation.", "questions": "- Can you better characterize when your gradient estimates are reliable? What happens on discontinuous functions where trees typically excel? Consider providing failure cases or bounds on estimation quality.\n- How do your gradient estimates compare to true gradients on known smooth functions? Can you show convergence behavior as tree depth increases?\n- What depth and sample size requirements are needed for reliable gradient estimation in different dimensions? Can you provide practical guidance for practitioners?\n- How does TBAS compare to established tree interpretability methods like SHAP values or permutation importance?\n- How does the method perform with categorical variables, missing data, or truly non-smooth functions that motivate tree usage?", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths\n- The core idea of extracting gradient information from tree structures is genuinely innovative and opens up new possibilities for tree-based interpretability.\n- The paper provides asymptotic analysis (Theorems 4.1, 4.2) establishing consistency of the gradient estimators under reasonable assumptions.\n- The method enables tree models to leverage existing gradient-based tools from other ML domains, potentially bridging interpretability techniques across model classes.\n- The gradient estimation can be computed in a single tree traversal, making it computationally attractive.\n- The evaluation covers multiple applications (active subspace estimation, integrated gradients, predictive improvement) across various datasets.\n\n### Weaknesses\n- Limited Scope of Application: The method requires \"sufficiently deep\" trees on \"well-behaved, differentiable functions.\" This significantly restricts its applicability since trees are often valued precisely for handling discontinuous or pathological data.\n- Questionable Fundamental Assumption: The paper's premise that regression trees can meaningfully approximate gradients of smooth functions contradicts why trees are typically chosen - their ability to handle non-smooth, discontinuous relationships.\n- Weak Empirical Results: Table 1 shows modest improvements that often fall within confidence intervals. The benefits don't strongly justify the additional complexity.\n- Incomplete Evaluation:\n- - No comparison to established tree interpretability methods (SHAP, permutation importance)\n- - Limited analysis of when the method fails or produces poor gradient estimates\n- - Missing evaluation on truly discontinuous functions\n- Presentation Issues:\n- - Heavy notation makes the core simple idea unnecessarily complex\n- - Some claims are overstated (e.g., \"first such linear sensitivity metric for trees\")\n- - The connection between gradient quality and tree depth could be made more explicit\n\n- Theoretical Limitations: The convergence rate of \\sqrt(P N^(-1) log N) may be slow in practice, and the assumptions (differentiability, sufficient depth) are quite restrictive.", "was_revised": true, "final_justification": "My concern still remains regarding the misalignment between theory and practice: the theoretical framework relies on continuously differentiability, while in empirical results the paper presents benchmarks that clearly violate differentiability assumptions, and claims this method works in practice. Without theoretical understanding of why their method works beyond its assumptions, the practitioners lack principled guidance for determining when the approach will be reliable. The empirical successes are encouraging, but the absence of supporting theory makes it hard to predict performance on new problems or identify potential failure modes.\n\nWith the concerns above, I will keep my rating as is.", "rebuttal": "Thanks so much for taking the time to carefully consider our work. We greatly appreciate it.\n\nWe'll now address the comments you made under \"Weaknesses\" and your questions. \n\n**Regarding Weaknesses**\n\nThanks very much for taking the time to think critically about our article. However, after careful consideration, we have found that we disagree with most of your weakness assessments. \n\nIn each bullet, the italics indicate what we are responding to, and the standard text is our response.\n\n- *Limited scope of Applications*: You are commenting on the scope of our mathematical results, not of our applications. In fact, many of our empirical results are on messy, real world applications, and provide empirical evidence that the method can perform well in this setting. \n- *Questionable Fundamental Assumption*: We’d like to challenge the frame of this assertion; we are in fact suggesting that trees are useful on additional classes of problems than they are typically selected for, including for friendly functions. \n- *Weak Empirical Results*: The strength of the result depends on the method used, with weaker results for individual trees and stronger ones for Random Forests. In practice, trees are commonly used within ensembling methods. On the random forest, our method offers significant improvement on 6/8 test problems, including halving the error on the popular keggu problem. Additionally, this criticism considers only 1 of 5 empirical applications. \n\n*Incomplete Evaluation*\n\n- *Incomplete Evaluation (1) - other methods*: The methods you’ve mentioned are for the importance of individual variables, not linear combinations of variables, and hence cannot be used to perform a linear rotation of the space like active subspaces or PCA. Since trees are invariant to scaling individual features, it is not clear how to include these methods in our experiments. \n- *Incomplete Evaluation (2) - Limited analysis*: Appendix C.1 shows how the method can fail if the tree depth is small relative to the function complexity. \n- *Incomplete Evaluation (3) - Missing evaluation on truly discontinuous functions*: Section 5.1 is on MNIST classification and Appendix C.5 consider classification versions of all our datasets, which manifests as a discontinuous function. The proposed method still seems to perform well. \n\n*Presentation Issues*\n\n- *Presentation Issues (1) - Notation*: We agree that the idea is much more intuitive than the notation. Believe it or not, the notation used to be even more burdensome, and we have spent much time thinking how to make it simpler, including providing figure 3 which illustrates all aspects of our notation. We welcome any specific advice for improved notation.\n- *Presentation Issues (2) - Some claims are overstated (e.g., \"first such linear sensitivity metric for trees\")*:  Of course, we acknowledge in the introduction that linear dimension reduction in general has been used in conjunction with trees, but to the best of our knowledge, the tree structure itself has not previously contributed to this dimension reduction. While we did perform a thorough literature review, it is completely possible that we have missed a previous linear sensitivity metric for trees, and in this event we would be very grateful if you could provide us a specific example of one.\n- *Presentation Issues (3) - The connection between gradient quality and tree depth could be made more explicit*: Theorem 4.1 gives a bound on the gradient error in terms of the number of splits in the tree. Under the assumption of uniform splitting, this is linearly related to the depth. \n\n--\n\n- *Theoretical Limitations The convergence rate… may be slow in practice*: We agree that there is always room for additional theoretical analysis about this method. However, our empirical studies demonstrate that the method does indeed work in practice.\n\n**Response to Questions**\n- Q: *Can you better characterize when your gradient estimates are reliable?*\n- A: We could envision interesting future work which uses a statistical test of linearity as is classically done in, e.g. ANOVAs combined with an estimate of the error variance to produce a bound on gradient quality. In the present work, we assessed reliability teleologically using out of sample prediction error. \n\n--\n\n- Q: *What happens on discontinuous functions where trees typically excel?*\n- A: From an applications perspective, we found that the method yielded useful results on a classification problem, which is of course discontinuous. From a mathematical perspective, using discontinuous functions complicates the analysis significantly, and would necessitate a different approach, since ours is based on Taylor’s theorem and thus first order differentiability. We view this as important future work.\n\n--\n\n- Q:  *Consider providing failure cases or bounds on estimation quality.*\n- A: Re failure cases: Figure 9 of the Appendix’s left column shows how a tree of insufficient depth fails to provide good gradient estimates even in large sample sizes. Re: estimation quality bounds: Theorem 4.1 provides an asymptotic bound on estimation quality. We view the development of finite sample bounds as interesting future work. \n\n--\n\n- Q: *How do your gradient estimates compare to true gradients on known smooth functions? Can you show convergence behavior as tree depth increases?*\n- A: Answering this question is the purpose of Appendix section C.1.\n\n--\n\n- Q: *What depth and sample size requirements are needed for reliable gradient estimation in different dimensions? Can you provide practical guidance for practitioners?*\n- A: Theorem 4.1 provides rates for the relative values of those quantities from an asymptotic perspective. As we mentioned in response to your first question, we could envision an interesting future approach which can provide this practical guidance by providing a finite sample bound of gradient error. But rather than constructing a tree guaranteed to achieve a particular gradient estimation error, we rather view practitioners taking the trees they are already using and applying the TBGE to it to see what it can tell them about their existing analyses.\n\n--\n\n- Q: *How does TBAS compare to established tree interpretability methods like SHAP values or permutation importance?*\n- A: As a linear dimension reduction method, it extends the variable-specific importance of SHAP and permutation to determining important linear subspaces. \n\n--\n\n- Q: *How does the method perform with categorical variables, missing data, or truly non-smooth functions that motivate tree usage?*\n- A: It’s not immediately obvious how this method would be applied to categorical variables. One clear option for addressing missing data would be to combine this method with multiple imputation. Though our mathematical results do not extend to nonsmooth functions, our empirical results, including on the MNIST classification, demonstrated useful behavior on discontinuous functions.\n\n\nThanks again for taking the time to carefully consider our work, and we look forward to having a great discussion during the rebuttal period."}, {"review_id": "LTZ9UT0djz", "reviewer": "Reviewer_XQAw", "summary": "This paper proposes a method to estimate the gradient of the underlying function from a regression tree estimator. With this estimation, one can improve the interpretation of the tree models.", "questions": "1. Theorem 4.1 shows a high-probability convergence result for a given point x. Is it possible to prove a similar conclusion that holds uniformly for all points in the domain, assuming the derivatives of f have some smoothness. \n\n2. The intuition of this proposed method relies on the fact that the a deep tree is fitted. However, in practice, when trees are used in boosting or random forest, each individual tree would usually not be very deep. Could the authors give a comment on the performance of the proposed method in that setting?", "limitations": "See weakness and questions.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength: The overall idea is an important extension of widely used regression tree models. The proposed algorithm is simple and intuitive. The authors have demonstrated the usefulness of this idea with a couple of applications. The paper is well-written -- I enjoy reading it a lot. \n\nWeakness: The theoretical guarantees are not very satisfactory. \nLooking into Assumption 1 in the supplementary material, it seems that Theorem 4.1 relies on an assumption that the mean of f(x) in a give leaf converges at square-root rate. This assumption itself need to be proved for many tree-fitting algorithms. For example, if one use CART to fit the tree, then the splitting threshold itself will be data-dependent, and one cannot directly claim the square-root rate from CLT.", "was_revised": true, "final_justification": "Thank you for the response. I will keep my rating.", "rebuttal": "Thanks very much for your kind comments and thanks as well for your careful reading of our math. Your comments on the weaknesses of our article have made us realize that we have poorly organized our assumptions. Theorem 4.1 was not aimed to be valid in the context of data-dependent splits; in the middle of the proof we state “...we are making cuts midpoints in each node…”, which was our target application. We meant to include this as part of Assumption 1.3, and have fixed this. Thanks for helping us realize this omission. \n\nWe now answer your questions:\n1) We think that a uniform convergence proof is possible, and indeed some of the assumptions of Theorem 4.1 are sufficiently conservative (such as bounding the diameter of the current leaf node by the maximum diameter of any leaf node) that we suspect this to be possible with only minimal modification of the proof. Please stand by, and we hope to provide the body of this proof before the end of the discussion period on 6 August. \n2) We think this is a very  interesting question, as indeed our numerical results of Section 5.2 actually seem to indicate that the advantage of using our method is greatest in small trees. We suspect that there is some sense in which the TBGE of a short tree is encoding information about the average gradient over the leaf node regions. And there is another side to the trade-off: a shorter tree stands to gain more from a good transformation than a deep one, which we think explains the observed numerical behavior. Investigating this phenomenon more fully would make for interesting future work."}, {"review_id": "T7Uja8zYqb", "reviewer": "Reviewer_ERhD", "summary": "This paper proposes a simple method to estimate the gradient of a target function in a piecewise-constant regression tree, as per Algorithm 1. This is used to approximate the Integrated Gradient and Active Subspace Method as per sec 2.3. A variety of experiments indicates the utility of this method for regression trees.", "questions": "Table 1: Please comment on the issue of the significance of differences, given my comments above.\n\nSec 5.1: Please clarify how x^* is chosen in these experiments. Also in Fig 4, should there be IG values for all pixels?\n\nGood answers to these questions would increase my overall score a bit.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Title: \"Regression Trees Know Calculus\" is a rather provocative title, attributing self-awareness (\"know\") to regression trees. A  more academic title would be something like \"Obtaining and Exploiting Gradient Information from Regression Trees\".\n\nEq 3: \\mu^r_i and \\mu^l_i have not been defined!\n\nSec 4: I did not check the proofs in detail (Appendix A).\n\nSec 5.1 (IG): Re Fig 4. IG requires two points x and x^*. It is not explained what these are in your experiments. I guess x is the current digit (e.g. the 0 in left most panel), but what is x^*?\nLacking this information I do not find Fig 4 useful. Also the gradient is estimated at all pixels, not just the black ones (anyway, as I recall MNIST pixel values are real-valued). Why are the values only shown for the black pixels, or are the other values near 0? It would be better to show the IG values per pixel without the digit in the background.\n\nAlso presumably this target function has only 2 values (e.g. +1/-1 for the two classes) -- so is a gradient actually well defined here?\n\nSec 5.2 Table 1. I appreciate the efforts to indicate similar performance, as per the caption \"bold indicates confidence interval overlaps with the lowest confidence interval\". But confidence interval at what level (alpha?). Also, bear in mind that you are using the same test set so can do *paired comparisons*. Overall Table 1 suggests that TBAS improves over the identity and PCA rotations. Please also refer to Appendix B.1 and Fig 8 from the main text, as additional information is provided there.\n\nMore broadly, Rainio, O., Teuho, J. & Klen, R., Evaluation metrics and statistical tests for machine learning. Sci Rep 14, 6086 (2024). https://doi.org/10.1038/s41598-024-56706-x provides a useful flowchart (Fig 3) and sttaistical tests for the comparison of different methods. \n\nSec 5.3: Please explain what the function you are estimating is in the main text. (It is given in B.2). Also define how you compute the \"active subspace error\" (perhaps angle in radians, cosine of angle??)\n\n* Other points\n\nPlease distinguish between textual and paranthetical citations\nproperly. e.g. l 103 should be (Constantine, 2015) not as written, and\nthere are many other examples.  I recommend natbib (e.g. \\citet, \\citep)\nfor doing this.\n\nl 112 easy-to-compute\n\nl 169: \\bold{a} is undefined. And why change notation from x to z?\n\nl 286: second principal component -> second active subspace component?\n\nFig 9. This figure is not comprehensible without the text in sec C.1. The graphics and caption together should *explain* the figure, so you need to explain what the colour coding means (angle between true and\nestimated gradient)in the figure. Check other figures similarly. \n\nQuality: Good. Although I did not check the asymptotic analysis results in detail (sec 4), I find these results credible. The experiments are quite well done, but see comments above re significance of differences\nin Table 1.\n\nClarity: Good. I found the paper quite well written, except for a few gaps highlighted above.\n\nSignificance: Good: Despite the high profile of (deep) neural networks, it is true that decision tree methods are heavily used in data science applications, and thus advancements for regression trees could have\nsignificant impact.  To me the strongest result in the experiments is Table 1, and the improvements made by TBAS rotation.\n\nOriginality: Good: AFAIK there has not been prior work on estimating derivatives in regression trees. Alg 1 is almost embarassingly simple -- it is probably what you would come up with if someone forced\nyou to estimate a gradient from a piecewise-constant regression trees. But still, it seems not to have been done before, and to be useful, and there is an asymptotic analysis of its properties.", "was_revised": true, "final_justification": "I was positive about this paper initially, and remain so after the rebuttals and discussion phase.\n\nReviewer XQAw raised an important point that \"the splitting threshold is data dependent, and that that one cannot directly claim the square-root rate from the CLT.\" The authors responded that their\nmidpoint split assumption they use for the proof is very common in the literature for trees (and gave examples). They clarified that they would enhance the discussion of the assumptions etc in the final\npaper.  I am satisfied by this.\n\nThe authors share with me a concern about the statistical significance of differences in performance, e.g. for Table 1. Another thought on this is that they might consider the frequentist correlated t-test\ndiscussed, e.g.,  in Benavoli et al (2017), which can handle correlations in results due to cross-validation. \nBenavoli, A., Corani, G., Demšar, J., and Zaffalon, M. (2017). Time for a Change: a Tutorial for Comparing Multiple Classifiers Through Bayesian Analysis. Journal of Machine Learning Research, 18(77):1–36.", "rebuttal": "Thanks very much for your positive review and for taking the time to carefully review our article. We respond in detail to all the points you brought up (shown in italics) and to your questions below. \n\n\n**Main Points**\n\n- *Title*: It’s true that the current title is not a classical staid academic title. But there is something to be said about titles which stimulate the prospective reader’s curiosity. Imagine if Vaswani et al had named their article “Attention mechanisms subsume other neural architectures on natural language tasks” rather than \"Attention is all you need\"...\n- *Eq 3: Mus not defined*. While we did define these in the first sentence of Section 3.1, we should have also included them in our notation illustration Figure 3 and now do so.\n- *Sec 5.1*: Thanks for pointing out that $\\mathbf{x}$ and $\\mathbf{x}^* $ are not defined in our IG experiment; this was an omission on our part and we have rectified this. You were correct in your assumption that $\\mathbf{x}$ is the current digit. $\\mathbf{x}^*$ is set as the all black image, i.e. with all entries equal to 0. You are correct that gradients are not well defined on this application. Nevertheless, the TBGE for any finite sample is, and in numerical experiments appears to behave reasonably.\n- *Sec 5.2*: Thanks for pointing out that we forgot to mention our confidence level; it is 95%. For the rest, please see below in the “Questions” section.\n- *Sec 5.3*: good point, we have moved that function’s definition to Section 5.2.\n\n**Other**\n\n- Thanks for pointing out our citation inconsistencies; we have gone through the text to rectify this. Apologies for any inconvenience this caused in reading.\n- *line 112*: thanks for pointing out this error which we have resolved.\n- “a” is simply the name of the argument for the function h; we now state as much.\n- Good catch regarding “principal component”; we’ve changed this.\n- We see what you mean regarding Figures 9-12 and have updated the caption information to be more informative.\n\n**Questions**\n\n- *Table 1*: Thanks for this question. \n\nFirst, it's worth mentioning that at the fundamental level of philosophy of frequentist statistics, there is no special advantage to doing a paired test relative to comparing confidence interval overlap, and each can be calibrated to have an arbitrary type I error rate. In the opinion of the statistician currently writing, it is an accident of history that paired tests are viewed as the “correct” procedure. Flow-charts can be a good starting point for research teams without access to statistical expertise, but ultimately determining the right statistical procedure for an analysis is a subjective decision which must be made in light of all domain and analytic information as well as the constraints of the medium in which the results will be presented. \n\nWe can think of two ways to deploy a paired test. In the first way, we would compare all methods to each other method, which would make for a more cluttered table, since we would have to assess significance of each test relative to each other test.\nIn the second way, we would compare only the best performing method to the other methods. \nBut this is not the hypothesis that is being assessed by the paired tests: it doesn't account for the randomness inherent in which method was the \"best\" performing one.\nWe would need to account for this using a more sophisticated statistical procedure. \nOn the other hand, confidence intervals are well understood and easy to present in this context. Hence our decision to go with them. \nBut ultimately, we are here deciding between flavors of ice cream (to use the classical example from moral philosophy), and there is no right answer. \n\n- *Sec 3.1*: Thanks again for pointing out this omission; as we mentioned above, x^* is the “zero image” consisting only of black pixels. This also explains why many pixels have an IG value of zero: it’s because they are zero for both the reference image and the text image, and hence the difference between x and x^* in expression 6 means the IG value will be zero as well. Some other cells with a nonzero x are also zero because no tree has split along that variable, and hence the gradient estimate is now zero. To aid with visualization, we show only nonzero IG values. We now state this explicitly in the figure caption. \n\nThanks again for your detailed comments and we look forward to the discussion period."}, {"review_id": "HR8w7eETJs", "reviewer": "Reviewer_UaXM", "summary": "The paper suggests a method to estimate derivatives/gradients for sufficiently large regression trees. On this basis, estimators which transfer the integrated gradient method and the active subspace method from neural networks to regression trees are developed. The experiments show applicability for local explainability of model predictions and promising results in different settings related to the active subspace method, in particular regarding active subspace estimation.", "questions": "1. As stated above, I am unsure about the feasibility of the assumptions for the (central!) theorems in Section 4 and the description/explaination is very brief. Could you elaborate whether they are typically fulfilled? Are there some clear conditions under which the assumptions are certain to be fulfilled? What is an example for not fulfilling the assumptions?\n2. As stated above, I would be interested in an examination of the relation to BSHAP (Sundararajan & Najmi 2020). From my understanding, this work (amongst others) discusses how splits in tree-based models encode gradient-like behaviors, which is a similar form of local explainability as well. \n3. The advantage of TBAS over the competing approaches seems to diminish for higher depth of the regression tree (cf. Table 1). Is this true and what is the reason for it?\n\nIf these questions are addressed satisfactorily, I may increase my evaluation score.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Quality: From what I can tell, the submission seems technically sound, and proofs are provided for the theoretical results. I appreciate that a variety of applications/experiments was shown, and found especially the study on local explainability of model predictions on MNIST to be intriguing. The results regarding active subspace estimation are also convincing. It is clear from the experiments and the discussion that much effort was expended; substantial additional material is contained in the Appendix.\n\nClarity: I found the paper to be mostly clear overall. The introduction of the concepts/methods, including the ones from literature (integrated gradient, active subspace), is generally well done. However, there is also potential for improvement. I am not sure why the “2” in the central equation (3) is needed. Figure 2 is not properly referenced, only in the caption of Figure 3, even though it greatly helps to understand how the method works. Figure 3 should be made bigger and introduced a bit later; currently, it is almost impossible to analyze as it is so small, and most of the notation explained is not yet introduced at this point in the paper. The theorems in Section 4 require assumptions which are only given in the Appendix, and I suggest to at least give a hint of what these assumptions are in the main body of the paper. Section 5.2 should reference to Appendix B.1 where the datasets for Table 1 are introduced. In addition, I was not able to assess the supplementary material (when extracting, it consists of a single file without file ending). There are also minor grammatical, spelling and consistency issues (inconsistent capitalization, repeated introduction of abbreviations etc.) that should be rectified.\n\nSignificance: The introduction does a good job in clarifying the motivation of the work and the background highlights important related concepts/methods. I was well able to understand the rationale behind the paper and am convinced that a gradient approximation for regression trees can be of great value and can advance understanding in a meaningful way. I also find both the applicability for local explainability as well as for uncertainty quantification to be highly intriguing. I am unsure about the feasibility of the assumptions for the theorems in Section 4, however.\n\nOriginality: With its novel methods, the paper seeks to improve understanding of regression trees and enable additional applications for this method, which I find to be very interesting as it may prove to be complementary to research on neural networks. A lot of implications and potential for future work are highlighted in the paper. The overall reasoning for originality is convincing. While a brief discussion of SHAP is provided in the paper, I would be interested in an examination of the relation to BSHAP (Sundararajan & Najmi 2020).\n\nMukund Sundararajan, Amir Najmi (2020). Proceedings of the 37th International Conference on Machine Learning, PMLR 119:9269-9278.\n\nIn sum, I found the paper to be a good read and wish the authors all the best for their work on this interesting topic.", "was_revised": true, "final_justification": "The paper suggests an interesting novel idea and shows a variety of applications, with convincing and intriguing results. The authors have thoroughly discussed all weaknesses and questions I brought up and provided clear, sound indication how they intend to address the weaknesses and resolve the questions in a camera ready version, including some helpful clarifications.\nI have also read the discussion regarding the proof of uniform convergence/the “splitting point at the midpoint of the cell” (which seem like two issues mixed up) and, regardless of outcome, do not think that this aspect is central to the paper and its main idea.\nThus, I overall keep my recommendation to accept the paper.", "rebuttal": "Thanks very much for your detailed comments on and positive assessment of our article; we are quite grateful for your time. \n\nBelow, we respond in detail to all the points you brought up (shown in italics) and to your questions.\n\n**Weaknesses**\n\n- *I am not sure why the “2” in the central equation...*: Great question: speaking at an intuitive level, it is because the mean terms are averages over the whole node, whereas in the denominator we have the extremes of the nodes. We've added this intuition to that section.\n- *Figure 2 is not properly referenced...*: Thanks for pointing out the lack of Figure 2 reference; we now refer to it in the introduction.\n- *Figure 3 should be made bigger...*: We agree that Figure 3 is a bit cramped. We would use the additional space in the camera-ready version to enlarge it and place it after the notation introduction.\n- *The theorems in Section 4 require assumptions which are only given in the Appendix...*: Responding to your question below has made us realize that we did a poor job discussing the implications of the assumptions. We have given some discussion in response to that question below, which we would include in a camera-ready version. \n- *Section 5.2 should reference to Appendix B.1 ...*: Yes great point, we have added reference to Appendix B to Section 5.2\n- *I was not able to assess the supplementary material...*: It is regretful that you were not able to access the supplementary material; we have just confirmed that we can download it and extract it from OpenReview on our Windows device successfully. It consists simply of Python code which reproduces every figure in the article. \n- *There are also minor grammatical, spelling and consistency issues*: We did indeed notice some grammatical issues etc when reviewing the article; we have now fixed several of these issues. Thank you for bringing this to our attention.\n\n**Questions**\n\n1. Thanks for this interesting question. In answering it, we have realized that our discussion of assumptions in the article was woefully inadequate, and would add some of the following discussion to the body of a camera-ready paper. The most important deviation of our theoretical assumptions from the typical deployment of tree-based methods in practice is the splitting behavior, namely Assumption 1.3. This states that splits alternate between variables, and it should also state that the splits are made at the midpoint of the cell (thanks to Reviewer XQAw for leading us to this omission). In practice, which variable is to be split, as well as the split location, depends on the data. However, this aspect may have a limited impact on our conclusions, because the fact that we will in practice split more often along impactful variables means that we are likely to build more precise estimates for larger elements of the gradient. We suspect, however, that the situation is actually improved for gradient estimates in practical algorithms relative to our simplified model. Of course, this discussion is at an intuitive level and a more rigorous mathematical examination would be interesting as future work. Assumption 1.1, which says that the predictors have a continuous distribution, may not be satisfied for certain data generating mechanisms which produce predictor variables only in certain submanifolds of the input space. In these circumstances, gradient estimation will of course be unreliable in locations of the input space in which we do not have data (as would be the case for function value estimation itself). Assumption 1.2, that the error converges at the square root rate, will generally be satisfied for iid data, but may be violated in the case of data with very strong spatiotemporal correlation which could trick the regression tree into modeling the error instead of the function. Most ML algorithms will suffer in this situation. Assumption 1.4, of a continuously differentiable function, holds for some of our case studies (namely 5.3, 5.4, 5.5) but not others (5.1 and potentially some of 5.2). We have demonstrated empirically that the gradient estimates are still useful without differentiability assumptions, but it is in our view interesting future work to study its behavior in this setting mathematically, which would require a completely different approach as series expansions would no longer be appropriate. \n\n2. Thanks for pointing us to this fascinating article which compares BShap to IG and other Shapley-derived sensitivity metrics. One clear difference between BShap and our proposed method is the requirement for the specification of a baseline value for BShap, much as is required for IG. Another is the way in which the methods compare function values: in BShap, a given feature is changed from fully at the baseline to fully at a given “explicand” (to use Sundararajan and Najmi’s term), while for the TBGE, the change becomes increasingly small as the tree depth grows. However, there are also similarities, as Sundararajan and Najmi  show that BShap satisfies linearity in the sense that the BShap value for a function f = h + g is the sum of the BShaps for h and g, a property of course shared by the gradient as well. We would add some of this discussion to the related work section of a camera-ready paper.\n\n3. We agree that the numerical experiments indicate that the performance is greatest in smaller trees, and we also noticed this in informal preliminary experiments. On the one hand, this is surprising because we only expect the TBGE to give a good gradient estimate if the tree is deep. But on the other hand, the potential for a data transformation to impact the accuracy of a tree is greatest if its depth is limited. It seems that this second factor is outweighing the first. We view as important future work a study determining the mathematical behavior of the TBGE in trees of finite depth. Though it may not converge to the gradient, it may nevertheless encode important information about the function. We have added some of this discussion to the conclusions and future work sections."}]

Author rebuttal:

Meta-review: The papers develops a way to estimate gradients of functions approximated using ensembles of regression trees.
The authors present an intuitive algorithm that is practically effective and demonstrate that the proposed method can consistently recover gradients.

Several referees raised concerns about the gap between practice and the assumptions on which the theory rests. In particular, concern was raised over the use of data-dependent splits in practice but midpoint splits in theory. I do not view this gap as specifically disqualifying and would like to thank the authors for a productive discussion around this point. I am encouraged that they see a path towards establishing similar theoretical results under weaker assumptions. 

I strongly encourage the authors to include a short remark in a revised version of the manuscript that acknowledges this gap and a few sentences in the discussion about how future work may bridge this gap. In doing so, please be sure to cite the additional papers referenced in the rebuttals. They should, of course, additionally follow through on the minor changes and clarifications raised by the referees and addressed in the discussion period (e.g., clarifying the midpoint split assumption in Assumption 1.3, editing captions for Figures 9-12, fixing typos and making sure notation is defined precisely, etc.)
Decision: Accept (poster)