On the Convergence of CART under Sufficient Impurity Decrease Condition
Authors: Rahul Mazumder
Haoyue Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: decision tree
CART

Abstract: The decision tree is a flexible machine-learning model that finds its success in numerous applications. It is usually fitted in a recursively greedy manner using CART. In this paper, we study the convergence rate of CART under a regression setting. First, we prove an upper bound on the prediction error of CART under a sufficient impurity decrease (SID) condition \cite{chi2020asymptotic} -- our result is an improvement over the known result by \cite{chi2020asymptotic} under a similar assumption. We show via examples that this error bound cannot be further improved by more than a constant or a log factor. Second, we introduce a few easy-to-check sufficient conditions of the SID condition. In particular, we show that the SID condition can be satisfied by an additive model when the component functions satisfy a ``locally reverse Poincare inequality". We discuss a few familiar function classes in non-parametric estimation to demonstrate the usefulness of this conception.

On the Convergence of CART under Sufficient Impurity Decrease Condition
Rahul Mazumder
Haoyue Wang
Sloan School of Management Massachusetts Institute of Technology rahulmaz@mit... teerrmmiiteee. edu
Operations Research Center Massachusetts Institute of Technology hacyuewSmit. edu
Abstract
The decision tree is a flexible machine learning model that finds its success in nu- merous applications. is usually fitted in recursively greedy manner using CART. this paper, we investigate the convergence rate of CART under a regression setting. First, establish upper bound the prediction error of CART under a sufficient impurity decrease (SID) condition [TQ our result improves upon the known result by (TO] under similar assumption. Furthermore, we provide exam- ples that demonstrate the error bound cannot be further improved by more than a constant or logarithmic factor. Second, we introduce set of easily verifiable sufficient conditions for the SID condition. Specifically, we demonstrate that the SID condition can be satisfied in the case of additive model, provided that the component functions adhere to a "locally reverse Poincaré inequality". We discuss several well-known function classes non-parametrra estimation illustrate the practical utility of this concept.
Introduction
The decision tree is one of the most fundamental and popular methods in the machine learning toolbox. It utilizes a flowchart-like structure recursively partition the data and allows to derive interpretable decisions. It is usually constructed in a data-dependent greedy manner, with an algorithm called CART [5). Thanks to computational efficiency and ability capture nonlinear structures, decision trees have served as the foundation for various influential algorithms for ensemble learning, including bagging (6, random forest 7 and gradient boosting [.]. These algorithms are among the best-known nonparametric models for supervised learning with tabular data [1].
Despite its remarkable empirical success in various applications, theoretical understanding of decision trees remains somewhat limited. The data-dependent splits employed in CART pose challenges for rigorous theoretical analysis. While some aasytto-analyze variants of CART have been widely studied [18 until recently. In particular, recent line of work [19] 24 10 [6] has established the consistency and prediction error bounds for CART and random forest. See Section [.] for a comprehensive review of related literature.
rigorous theoretical analysis of the original version of CART has been absent
In this paper, we study the decision tree under a nonparametric regression model:
(Ix) + i [n]
(1)
with (xx (1) ...,, E RP, D E R; is the noise with zero-mean, and f*(xx) is the signal
function. We consider a random design where {zr)r_ are i.i.d. from some underlying distribution
supported on [o, 11, and {eihi are i.i.d. independent of {x,]a For an estimator f of f*, we use
"This work is supported by Office of Naval Research -N00014-1--1-8800
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the L prediction error 1
measure of the estimator f. Consider regression tree algorithm that produces heuristic (not necessarily exact) solution f of
Σ((())- - -))) JETa
min
(2)
where Ta is the space of binary (i.e. each splitting node has two children) axis-aligned regression trees with maximum depth d. The statistical performance of the estimator f. therefore, is affected by the following three factors: (i) Approximation error: how accurately can f be approximated by a regression tree in Ta. (ii) Estimation error: the variance of the estimator, which is affected by the complexity of the function space Ta. A larger space Ta (i.e. larger d) can reduce the approximation error, but it may also increase the estimation error and lead to overfitting. (iii) Optimization error: the discrepancy between f and the exact optimal solution of the optimization problem (2). Indeed, if f is the exact optimal solution of (2) (i.e. optimal regression tree), it can approximate a broad class of can be analyzed via the classical theory of least-squares estimators 13 However, since solving (2) to optimality is computationally challenging for large-scale data, heuristies like CART are typically employed in practice. To understand the statistical performance of CART, the major difficulty lies in the analysis of the optimization error of CART.
f [9] and the prediction
As greedy algorithm, CART examines only one split in each iteration (see Section 1.3 for details). Although decision trees are intended to capture multivariate structures across different features, the greedy nature of CART poses challenges in approximating functions f* that have complex multivariate structures. For example, consider the two-dimensional "XOR gate" function f (u) := [iuejo.1/2)) + 1 (11 [14, and assume that z; has uniform distribution on [0, 1J2. Note that f itself is depth-2 decision tree, with (e.g.) the root node split with the first coordinate 1/2, and the left and right children split with the second coordinate at 1/2. However, due to the symmetry structure of f*, when the sample size is large, the root split of CART is completely fitting to noises and is likely to generate split near the boundary [5] 8). Consequently, the resulting estimator f fails to capture the true tree structure encoded in f" The major difficulty in fitting the XOR gate function with CART lies in the complicated interaction between the two coordinates.
The discussions above naturally lead to the following two questions about CART:
What conditions on f* are needed such that CART can approximate f" and yield consistent estimator?
If f* satisfies such conditions, what is the convergence rate of the prediction error of CART?
In this paper, we aim to address these fundamental questions by providing sufficient conditions on f* such that one can establish convergence rates of CART. These sufficient conditions are quite flexible to include a broad class of nonparametric models. In the following, we first discuss some related literature and the basics of CART. In Section 2 we prove general error bound for CART under sufficient impurity decrease (SID) condition [10 of s This error bound is an improvement over the existing results under similar conditions
[10). In Section we introduce sufficient condition for the SID condition on fr, and use it to show that the SID condition can be satisfied by a broad class of f*.
1.1 Related literature
The inception and analysis of decision trees and CART algorithm can be traced back the seminal work of Breiman [5). Breiman's 's study marked the first significant step towards establishing the consistency of CART, albeit under stringent assumptions concerning tree construction. The original formulation of CART, characterized by data-dependent splits, poses challenges when it comes to rigorous mathematical analysis. To address this issue, subsequent research efforts [8] 4 have introduced alternative variants of CART that lend themselves to more tractable theoretical examinations. For instance, certain studies [12 in the tree. Other approaches incorporate random selections of splitting thresholds [12] 2), while some restrict splits to occur exclusively at the midpoint of the corresponding cell in the chosen coordinate (3) These simplifications ensure the independence between the splitting rules of the
assume random selection of splitting features
tree and the training data- the tree depends on the data only via the estimation in each cell. Such independence simplifies the analysis of the resultant trees. In similar vein, alternative strategies have

---

been proposed. such as the employment of two-sample approach [23] to compute splitting rules and cell estimations separately, giving rise what is known as an "honest tree". This methodology also ensures independence between various aspects of the tree construction and estimation process.
Since the first consistency result in (5), the strict theoretical analysis of the original CART algorithm has remained elusive until recent advancements. A significant breakthrough came with the seminal work of Scornet al. [9], which demonstrated the consistency of CART under the assumption of an additive model [15] with continuous component functions. It makes a technical contribution on the decrease of optimization error of CART. This techmical argument strongly relies on the additive model. Subsequent works [17 [6] further extended the theoretical analysis by providing non- non-asymponn ayypttii error bounds for CART under a similar additive model. However, the rates derived in [17 [6] is a
slow rate of ((log(n))) which seems not easy to be improved under the same assumption [8] Although the additive model a well-studied model in statistical learning, it is not immediately evident why such modeling assumption is specifically required for CART to function effectively.
Another line of work [0] adopts more intuitive assumptions on the signal function f to ensure the progress of CART. In particular, Chi et al. [00] introduced a sufficient impurity decrease (SID) condition. In essence, the SID condition posits that for every rectangular region B within the feature space, there exists an axis-aligned split capable of reducing the population variance of f* (conditional on B) by a fixed ratio. Note that such a split cannot be directly identified by CART, as it necessitates knowledge of the population distribution of 2,. Instead, CART employs empirical variance of yi!=1 to guide its cell splitting decisions. Nonetheless, the SID condition strong assumption on the approximation power of tree splits, which can ensure the consistency of CART via an empirical process argument [10 A similar condition has also appeared implicitly in [24]. Under the SID condition, Chi et al. I0] studied the consistency and convergence rates of CART, demonstrating a polynomial convergence O(n of the prediction error. A possible limitation of the SID condition is the difficulty of verification: it necessitates the decreasing condition to hold true for all rectangles. Although few examples are provided in [10, the general procedure for verifying whether specific / satisfies this condition remains unclear. Notably, its relationship with the additive model assumption in 19 remains to be fully understood.
Lastly, it is worth mentioning that several recent studies (20 g have investigated the performance lower bounds of CART, shedding light on its limitations. Specifically, Tan al. 20) demonstrated that even when assuming an additive regression function f", any single-tree estimator still suffers from the curse of dimensionality. Consequently, these estimators can only achieve convergence rates considerably slower than the oracle rates established for additive models [21]. Another study by Cattaneo et al. [8] delved into the splitting behavior of CART and provided theoretical support for empirical observations (5) indicating that CART tends to generate splits near boundaries in cases where the signal is weak. These lower bounds support the importance of using trees in ensemble models to reduce the prediction error. Although we focus analyzing CART for single tree in this paper, the result can be adapted to the analysis of ensembles of trees for the fitting of more complex function classes.
1.2 Contributions
The first contribution of our paper is refined analysis of CART under the SID condition. Although the convergence of CART has been studied in [10] under SID condition, the analysis of [10] seems not tight when the noises have light-tails (see discussions in the Appendix C). We establish an improved analysis of CART under this setting, and show by examples that our error bound is tight up to log factors.
The second contribution of this paper is the decoding of the mystery of the SID condition. We discuss a sufficient condition under which the SID condition holds true. In particular, we introduce class of univariate functions that satisfy an locally reverse Poincuré inequality, and show that additive functions with each univariate component being in this class satisfy the SID condition. This builds a connection between the two types of assumptions in the literature: additive model and SID condition. We discuss a few examples that how the locally reverse Poincaré inequality can be verified.
3

---

1.3 Basics of CART
We review the methodology CART to build the tree. The primary objective decision trees is to find optimal partitions of feature space that produce minimal variance of response variables. CART constructs the tree and minimizes the variance using a top-down greedy approach. starts with a root node that represents the whole feature space R this can be viewed as initial tree with depth O. At each iteration, CART splits all the leave nodes in the current tree into left child and a right child; the depth of the tree increases by 1, and the number of leave nodes in the tree doubles. At each leave node, it takes an axis-aligned splits with maximum variance (impurity) decrease. Let & be the set of all intervals (which can be open, closed, or open one side and closed another side). Define the set of rectangles in [0, 1|2 as:
P II
Bg BYErvjell
For each A E A. define IA = {i E [n] xi E A}. For leave node that represents rectangle E A, the impurity decrease of split feature j E [p] with threshold E R is given by:
((A,J,b)
Σ (u=
UIA)
1
Σ
1 (ys ÚIAL n
Σ iEIAR
(yz
ÚI
(4)
VEZA
n
(EIA,
AR
where yI = [7]
EiET Vi for any I _ [n]] and
Ar bz( = An [0, | S b), Ag = AR(İ, b) = An (n (0, 11" 1 > b}.
(5)
To split on A, CART takes j and i that maximize the impurity decrease, i.c.,
3, argmax b) jElp),bE(o.1]
(6)
This splitting procedure is repeated until the tree has grown to a given maximum depth d.
1.4 Notations
For a, b O, we write O(b) if there exists a universal constant C > 0 such that S. Cb; we write = (a) if a = Obb) and write a = ((b) if both a (b) and a = (2(b) are true. For values an,ps bn.p that may depend on n and p. we write an,p = pb if an.p = O(b log" (np)) for some fixed constant y 0.
2 Error bound of CART under SID property
We study the prediction error bound of CART for the regression problem 1I. We focus on a random design as the following assumption.
yr Assumption 2.1 (i) (Random design) Suppose {x,)=,, are i.i.d. random variables with distribution
supported on [0. 1p. Suppose μ has a density px (w.rt. Lebesgue measure) on [0, 1]2 satisfying
0 < 0 S px) & θ < for all [0, 1]" for some constants @ $ 1 and Ø 2
(ūi) (Error distribution) Suppose {<:]== are iidd zero-mean bounded random variables with lea I m < oc for some > O. Suppose (c:) are independent to {x:)
(ii)) (Bounded signal function) Suppose suPwelo.iIp (f)) M oo for some constant M.
In Assumption 2.1 (i), it is assumed that the features I; are supported on [0, 1]2 for convenience. The same results (different by at most constant) can be proved if we replace j0, 1|2 with an arbitrary bounded rectangle. The second assumption (Assumption 2.1 (ii)) requires the error terms (es 1n to be i.i.d. bounded - this is the key difference of our paper and the assumptions made 1Q]. In particular, [10] made milder assumption on the error terms that allows them to have heavy tails. Their result, however, when specifying to the case of bounded noises, is not tight (sec

---

discussions in Appendix for for a comparison). Note that for convenience we have assumed that & is bounded. If instead, we assume the noises are uub-Gaussian, similar conclusions can also be proved via truncation argument (the bound may be different by log factor). The third assumption (Assumption 2.1 ( a standard assumption for nonparametric regression models 22 K
Under the random design setting in Assumption 2.1 we are ready to introduce the sufficient impurity decrease condition on the underlying function f Let X be random variable in Iº that has the same distribution as I and is independent to {T1, ... InJ. For any A E A.j E [p] and b E R, define:
()) = P(X A)Var(f (X) E A) P(X Ar)
Ar.) (7)
P(X E An) (n) E An)
where Ar. and Ar are defined in ( and (xr) A) means the conditional variance defined as
Var(f"(XX)X E A) = E (
E A))"(x EA)
(8)
is not hard to see the similarity between (,) and Í(A,j, 6) (defined in (4)) where the former can be viewed as population variant of the latter. Intuitively, for a split with feature and threshold A ((A, j. b) measures variance decrease of f after this split. The SID condition below assumes that there is split with large variance decrease.
Assumption 2.2 (Sufficient Impurity Decrease) There exists a constant À E (0, 1] such that for all A E A.
sup JE(p),ER
(,), 2 A P-P (X)xx A)
Note that Assumption 2.2 a condition depending on both the function f and the underlying distribution X jr. Briefly speaking, the SID condition requires that the best split must decrease the population variance by a constant factor (note that À is required to be bounded away from 0). Intuitively, the condition (9) can be satisfied if f has significant "trend" along some axis in A, but may be hard to satisfied if f* is relatively "flat" in A. Since Assumption 2.2 requires ( being satisfied for all cells A E A, it essentially requires that f is not "too flat" on any local rectangle A. In Section 3 we develop a technical argument to translate this intuition into a rigorous statement, and use it to check Assumption 2.2 for wide class of functions.
With Assumptions 2.1 and 2.2 at hand, we are ready to present the main result in this section. For any (1)) denote the 1,2-norm of with respect to the measure /z.
function g IR RR, let
Theorem 2.3 Suppose Assumptions 2.1 and 2.2 hold true. Let (-) be the tree estimated by CART
with depth Suppose n is large enough such that 2Be2d log(T2p" (n=1)ad < 3/4. 4. Then there exists universal constant C > O such that with probability at least 1 -8, it holds that for any > O.
2d (dllg(())) + log(1 122
(l - 1 & 2Var((((X))
(1- (1+ap) +
(10)
an
where U = M + m. In particular, taking 1/d and d = (n)g(n)) logg a)) it holds
1 1000-f112e 122(x I SCN,U log2 (n) log(np) + log(n) log( (
(11)
(((())
(1- and Cx,u is constant that only depends on À and U. where o()) = T-logg(1-X)
The error bound in 110 consists of two terms. The first term corresponds the bias of the approx- imating f using CART. It decreases geometrically as d increases, which is suggested by the SID condition. The second term is ((2ddlog(pp))/n log(np)/n), which corresponds the estimation variance of CART. Here the term 2d represents the model complexity
fully-grow grown depth d tree has 2d leaves. The proof of Theorem 2.3 is presented in Appendix A It is based on a careful technical argument that controls the difference between the population impurity decrease A(A, j. b) and the empirical impurity decrease (AA.j.b) particular, our analysis different from that of [10]. Note that [0]] makes a different assumption the error distribution, and their technical argument is not sufficient for the proof of Theorem 2.3 Partieularly, the error bound (T] is an improvement of the results Section Cor detailed comparison.
proved in Theorem 1 of [10
5

---

Note that the convergence rate in 111 has crucial dependence on the coefficient A. For a large value of X, the exponent (AA) is also larger, leading to a faster convergence rate in (TT). On the other end, if Á is small, as À O, we have (A)) - 0, and the convergence rate in (11) can be arbitrarily slow. Nonetheless, as long as the SIID condition is satisfied with À bounded away from 0, (TT) shows
polynomial rate, which is better than the logarithmic rate in [6] without the SID condition.
To explore the tightness of the error bounds Theorem 2.3 we consider simple example with being a univariate linear function.
and 3s are i..dd from the uniform distribution on (0, }.. Suppose f is univariate linear function: (t) L. Then the SID condition
Example 2.1 (Univariate linear function) Suppose p
(Assumption 2.2) is satisfied with coefficient X 3/4. As a result, holds (()) = 2/3, and the error bound in the RHS of (11) is Ö(n
Proof. For any interval = [e,r], we have
P(X E ()Va((((X)IXEE () E)= { (1-
l +
di (r- f)3
(12)
12
Take b : (8 + r2/2, then we have
1/ (+r
/"
b
(t
b+b
dt 1-" (t
b b+r
A(A,1,6) =
df
dt
2
Je
2
2
(13)
1
1
3
f)3
(b
8)3
(r
b)3
8)3
12
12
12
48
Combining 12 and
13
we know that Assumption
2.2 is satisfied with 3/4.
As shown by Example 2.1 when f a univariate linear function and { are from uniform
distribution, the error bound in (TT) reduces to (n (2/3). This rate matches the lower bound for any partition-based estimator (see e.g. cannot be improved (by more than log factor) via any refined analysis. To verify the rate O(n 2/3). we conduct simulation shown by Figure [ In particular, Figure presents the log-log plot of the prediction error of CART versus different sample sizes, where the depth is taken as stated above (T)) A reference line of slope -2/3 2/3 is also shown. It can be seen that the slope of the line for CART
Chapter 4), hence showing that the upper bound in II]
also roughly -233, which is consistent with the rate Ö(n 2/3) derived in Example 2.1
-6.5
reference line
1'1
-7.5
log
-8.5
7.0
7.5
8.0
8.5
9.0
9.5
10.0
10.5
log(n)
Figure 1: Prediction enror of CART versus sample size n for a univariate linear model.
Chapter 4 and the upper bound in Theorem 2.3 The lower bound in [3] requires that the splitting points of the partition are independent of the training data, while for CART this condition not satistied.
TThere is a subtle difference between the lower bound 13

---

3 Function classes satisfying SID condition
In this section, we introduce class of sufficient conditions that facilitate the easy verification of the SID condition for broad range of functions. Specifically, we focus on the case when f has an additive structure:
(14) where fs's are univariate functions. Note that additive model has also been assumed in prior works such as [99 17 [6 for the study of CART. If we only assume that each component function fj
(*()) = (u4 + (22) + +.... (Tpp)
has bounded total variation, then only slow rate Ollo (n)) is known [17]. In the following, we discuss few sufficient conditions concerning the component functions fj under which f satisfies the SID condition, consequently guaranteeing faster convergence rate as indicated by Theorem 2.3
First, we introduce key class of univariate functions that satisfy special integral inequality.
Definition 3.1 (Locally Reverse Poincaré Class) For a univariate differentiable function g on an interval Q C. R. we say it belongs to the Locally Reverse Poincaré (LRP) class on Q with parameter T for any subinterval [a.b] S Q.
(L (((())
2 S b- =
72
inf [ WEB
(9(1) w/2 dt
(15)
We use the notation LRP(Q.T) to denote the class of all such functions.
is worth noting that for any given univariate differentiable function and a fixed interval [a, 6]. there exists constant such that the reverse of inequality (15) holds true, established by the Poincaré inequality. The condition (15) requires a uniform constant T > O such that the reverse of the Poincaré inequality holds true. Note that the LHS of (15) is equivalent to the square of the total variation of on [a, b). and the RHS is a constant multiple of the conditional variance
on
[a, (under the uniform distribution). Intuitively, this condition can be satisfied when the function g exhibits a clear "trend" within any interval (a, bj rather than being fuzzy fluctuations. We give a few examples below.
Example 3.1 (Strongly increasing function) Let g be a strictly increasing function on [0, 1] with 22 2 g(( 2 c for all & E [0, 1]. Then E LRP 11,2//e2/(11
Example 3.1 provides direct generalization of the simple linear function showcased in Example 2.1 Note that this example was also discussed in [T0] In Example 3.1 since g' (1) is consistently bounded away from zero, verifying the inequality 15 becomes straightforward. Below we present more nuanced example where g (t) may equal zero at certain point E [0, 1].
Example 3.2 (Smooth and strongly convex function) Let g be L-smooth and o-strongly-comvx function on [0, for some L
0, i.e.,
- [ [1-s)) 8)² s s(() g'))) 8) - (1 s)²
(16)
2
for all 8 E [0, 1]. Then LRP((0, 1), 110(L/o))
Note that for smooth and strongly convex function g, the gradient gt) can be zero some E [0, 1]. But the strong convexity condition guarantees that there is at most one point t where g'(t) 0, and the inequality (15) can still be satisfied. Additional details can be found in Appendix B
Example 3.3 (Polynomial with degree r) There exists a constant C, that only depends on r such that for any univariate polynomial g of degree at most T, g E LRP C.).
Although the set of polynomials (with a degree at most r) appears to be complicated, it is finite- dimensional linear space. Therefore the differentiation is bounded linear operator between finite dimensional normed linear spaces. As a result, the conclusion of Example 3.3 can be proved via a variable transformation argument. See Appendix B for details.
Examples 3.1 3.3 demonstrate that the LRP condition can be readily verified for various well-known function cl classes, but the relationship between the LRP class and the SID condition remains unclear. Below we present the first main result this section, which establishes a connection between the LRP class and the SID condition under the additive model.
7

---

Proposition 3.1 Suppose Assumption 2.1 holds true, and f has an additive structure as in 14 fi E LRP((0, 1], r) for all [p]. then Assumption 2.2 satisfied with X = 40/ (l//ppp0)
As shown by Proposition 3.1 for the additive model (14), when the basic conditions in Assumption 2. satisfied, the SID condition holds true for I as long as each component function is in an LRP class. Particularly, the SID condition is satisfied for component functions from Examples
3.3
Note that the coefficient in Proposition 3.1 is proportional very small when p is large. In particular, with this X = (L1/p) (with 0, 0 and T being constants), by
1/p, which implies that it can be
Theorem 2.3 the prediction error bound in the RHS of (T] is 0//=) for some constant > 0 Since the exponent is dependent on p. the curse of dimensionality becomes evident. This seems to indicate that the analysis of Proposition 3.1 could potentially be refined. However, given the negative
results demonstrated by [20 8 is likely that for tree-based estimators, even with the additive model, the curse of dimensionality cannot be circumvented.
Proposition 3.1 requires each component of the additive function to lie in an class. Actually, this condition can be further relaxed as in the following proposition.
Proposition 3.2 Suppose Assumption 2.7 holds true, and f has additive structure as in (4
Given integer r 2 and constants a > 0. 2 1. Suppose for each k E [p] there exist
t 2 a/r and fā LLRP((t-1,,),,9) for all) j [r]. Then Assumption 2.2 satisfied with parameter 0/(p0r2) where 72
(K)
(R)
(k) with (k) (k)
2n p²
max m9x 32 + 8²}.
max
2a
By Proposition 3.2 an additive function f satisfies the SID condition if each component function is a piecewise function, with each piece belonging to an LRP class. Notably, continuity at the joining points of consecutive pieces is not necessary. However, for technical reasons, it is required that each piece has a length that is not excessively small, as determined by the parameter a. See Appendix B for the proofs of Proposition and and 3.2
4 Proof sketch of Theorem 2.3
We provide sketch of the proof of Theorem 2.3 For p 2 1 and d 2 1, define
Ap.d IIIG, my) E
#(j E [p] [ mg] * [0, 1]} < d)
(17)
That is, each rectangle in Ap.d at has at most d dimensions that are not the full interval [o, 1]. When p 2 d, Ap.d contains all the rectangles in 1|" i.e. Ap.d A. However, when d is much smaller than p (in a nigh-dimensional setting), Ap.d contains much fewer rectangles than A. Note that for decision tree with depth d, each leaf node represents rectangle in Ap.a-
The proof of Theorem 2.3 builds upon few technical lemmas which provide uniform bounds between the empirical and populational quantities. These results may hold their own significance in the study of other partition-based algorithms. For d E (0, 1). define values
4 (6) = f, n, d) = log(2p 1)22/1))
T2(6) n. 20ddd log(p (n + 1)2d
(18)
n
E(6) i(5, n, d) = [1 d) n,,
where Ō is the constant in Assumption 2.1 (i). Note that we have T(6) < 0 (log(1))) We have the following uniform bounds on empirical and populational mean on every rectangle in Ap.d.
Lemma 4.1 Suppose Assumption 2.1 holds true. Suppose (2(1/2 < 3/4. Then with probability at
least 1 - 8, it holds
sup AEAp,
PP(X B(J E A) UIA s 200 (
(19)
'The lower bound is based on general additive models which may not satisfy the SID condition. When the SID condition is satisfied, the lower bound may be better.
8

---

For tree- based estimator in practice, the prediction at each leaf node is usually given by the sample average of yi for all the samples routed that leaf, i.e., the value YA for a leaf with rectangle A. Therefore, Lemma 4.1 provides uniform bound on the error if we replace the prediction at each leaf by the populational conditional mean (X
A). It is worth noting that the gap between DA and [X) E A) is rescaled by the quantity vP(X E A). Intuitively, when the rectangle A is small and hence P(X E A) is small, few points are routed to the rectangle A. As result, the corresponding gap between VA and [f (X) E A) can be large- which leads to a large discrepancy of the estimate and the signal locally in this cell A. However, in another perspective, since the cell A is small, a large discrepancy in A only makes a small contribution to the overall error f -f (x)) Therefore, the factor /P(X E A) in the LHS of (9 is proper balance of these two aspects. This is the key technical argument that differs from the analysis in [TO]. It helps establish the tighter bounds in Theorem 2.3
Lemma 4.2 Suppose Assumption 2.1 holds true. Given a constant a > O. Given any 8 E (0, 1),
suppose (2(6/36) < 3/4. Then with probability at least 1 - 6, it holds
AAA j. b) (1 a ( (1+1/
A E Ap.d-1 [p], b b R
b) S (1 + a b) + (1+1//)
A A E Ap.-11 j E [p), b
for some universal constant C" O.
Lemma 4.2 establishes upper bounds on the discrepancy between empirical and populational impurity decrease. builds an avenue to translate the SID condition into an empirical counterpart, which is further used to derive the decrease of objective value.
With Lemmas and hand, we are ready wrap up the proof of Theorem 2.3 First, we have
(1 -f < 2 - 7 (12x(x) + + - 11 == (k) + 2J2(k) (20)
where f(()) is a tree with the same splitting rule as f(k) but leaf predictions replaced by the populational means (in that leaf). The term (k) can be bounded
J2(k) = Σ P(X E A)) E A,, BIN,)² S CCU22 h klog(np) + log (1/5)
tEC(A)
where ((k) is the set of leaves of f(t) at depth k; A, is the corresponding rectangle for a leaf I; and C a universal constant. The last inequality (2T) is by Lemma The term J1 (k) can be written as
(1k
Σ P(X Al2T) Var(f xT)
tEC())
Making use of Lemma 4.2 and by some algebra (see Appendix A for details), recursive inequality can be established:
(1 a1) Ji(k) + 2 (K'(kllg(mp)) + log(1/0))
Ji + 1)
The proof of Theorem 2.3 complete by telescoping the inequality above, and combining the upper bounds for (k) and (k) with 20
5 Conclusion and discussions
We have proved an error bound on the prediction error of CART for a regression problem when f satisfies the SID condition. This error bound cannot be improved by more than a log factor. We have also discussed a few sufficient conditions under which we can show that an additive model satisfies the SID condition.
One possible limitation of this work that: it seems that the SID coefficients À derived in Section are not tight. Since À appeared in the exponent of the rate in Theorem 2.3 tighter estimate of leads to an improved convergence rate We leave it as a future work for a more precise analysis of the SID condition.

---

References
[1] Abhinect Agarwal, Yan Shuo Tan, Omer Ronen, Chandan Singh, and Bin Yu. Hierarchical shrinkage: Improving the accuracy and interpretability of tree-based models. International Conference Muchine Learning, pages 111-135. PMLR, 2022.
[2] Sylvain Arlot and Robin Genuer, Analysis of purely random forests bias. arXiv preprint 2014.
[3] Gérard Biau. Analysis of a random forests model. The Journal of Machine Learning Research, 13(1):1063- 1095, 2012.
[4] Gérard Biau, Luc Devroye, and Gäbor Lugosi. Consistency of random forests other averaging classifiers. Journal of Machine Learning Research, 9(),, 2008.
L Breiman, JH Friedman, R Olshen, and CJ Stone. Classification and regression trees. 1984.
[6] Ico Breiman. Bagging predictors. Machine learning, 24(2):123-140, 1996.
Leo Breiman. Random forests. Machine learning, 45(1):5-32, 2001.
[8] Mattias D Cattanco, Jason M Klusowski, and Peter M Tian. On the pointwise behavior of recursive parti- tioning and its implications for heterogeneous causal effect estimation. arXiv preprint arXiv:2211.10805, 2022.
[9] Sabyasachi Chatterjee and Subhajit Goswami. Adaptive estimation of multivariate piecewise polynomials and bounded variation functions by optimal decision trees. The Annals of Statistics, (9K5):25312255) 2021.
[10] Chien-Ming Chi, Patrick Vossler, Yingying Fan, and Jinchi Lv. Asymptotic properties of high-dimensional random forests. The Annals of Statistics, 3016):3415-3438 2022.
[11] Jerome Friedman. Greedy function approximation: gradient boosting machine. Annals of statistics. pages 1189-1232, 2001.
[12] Robin Genuer. Variance reduction in purely random forests. Journal of Nonparametric Statistics, 24(3)5433 562, 2012.
[13] László Györfi, Michael Kohler, Adam Krzyzak, Harro Walk, et al. A distribution-frre theory of nompara- metric regression, volume 1. Springer, 2002.
[14] Trevor Hastie, Robert Tibshirani, Jerome H Friedman, and Jerome H Friedman. The elements of statistical learning: data mining, inference, and prediction, volume 2. Springer, 2009.
[15] Trevor Hastie. Generalized additive models. Statistical models in pages 249-307. Routledge, 2017.
[16] Klusowski and P Tian. Large scale prediction with decision trees. Journal of the American Statistical Association, 2022.
arXiv preprint [17] Jason M Klusowski. Universal consistency of decision trees in high dimensions. arXiv:2104. 13881, 2021.
[18] Lin and Yongho Jeon. Random forests and adaptive nearest neighbors. Journal of the American Statistical Association, 101(474)5578-590, 2006.
[19] Erwan Scornet, Gérard Biau, and Jean- Jean-Philippe Vert. Consistency of random forests. The Annals of Statistics, 43(4):1716-1744 17416611112220 2015.
[20] Yan Shuo Tan. Abhineet Agarwal, and Bin Yu. A cautionary tale on fitting decision trees to data from additive models: generalization lower bounds. In International Conference Artificial Intelligence and Statistics, pages 9685. PMLR, 2022.
[21] Zhiqiang Tan and Cun-Hur Zhang. Doubly penalized estimation in additive regression with high- dimensional data. 2019.
[22] Alexandre Tsybakov. Nonparametric estimators. Introduction to Nonparametric Estimation, 2009.
[23] Stefan Wager and Susan Athey. Estimation and inference of heterogeneous treatment effects using random forests. Journal of the American Statistical Association, 113(623):1228-11 2018.
[24] Stefan Wager and Guenther Walther. Adaptive concentration of regression trees, with application to random forests. arXiv preprint arXiv:1503.06::: 2015.
10

---

A Proof of Theorem 2.3
A.1 Notations
We first define some notations in the context the model (T. For p 2 and d 2 1, define
{
[I us] E E #(J E [e, uy] * (0, 1]} s d} j=l
Ap.
(21)
That is, each rectangle in Ap,a has most d dimensions that not the full interval [0, 1]. Note that for decision tree with depth d, each leave node represents a rectangle Ap,a. Furthermore. for (0, 1). define values
(6) (,,
log(2p" 1)
(0) = n, 20c²d V log(p" (n 18)
(22)
n
n
E(66 F(6,, n, E1 n, (2 n,
where 0 is the constant in Assumption 2.1 (i). Note that have f(8) S O(dlog(mp/6)/m)
For values a, > write S b if there is universal constant C such that S Cb. We write if there constant C, that only depends on r such that S C.
A.2 Technical lemmas
Now we can introduce the major technical results to establish the error bound.
Lemma A.1 Suppose Assumption 2.1 holds tree. Suppose lz(6/12) < 3/4. Then with probability at least
1 8, it holds
sup Ap.
P(X E A) B( A) UUZA
s 200 (E6/12)
(23)
The proof of Lemmaa..1 presented Section A.4 Note Lemma A.1 provides uniform bound gap between the populational mean ((f"(X)] (X)] E A) and the sample mean UI This is used to derive the geometric decrease of the bias, using the SID assumption.
Lemma A.2 Suppose Assumption 2.1 holds true. Given any E (0, 1), suppose (28/44) < 3/4. Then with probability at least 8 it holds
sup AEAp
5
(24)
The proof of Lemma A.2 is presented in Section square root of probability and sample frequency over all Ap.a. Note that this uniform bound is stronger than result without square root (which can be obtained easily via Hoeffding's inequality and union bound), and is useful to prove the final error bound Theorem [2.3
A.5
Lemma A.2
provides uniform deviation gap between the
For any rectangle E A. j E [p] and E R., define
(A,j,bb = F(X E AL) (BU E A) - -((((X E AL))?
(R(A,j,b = P(X E AR) AR) (B( A) -() e AR))
Âz (A, = IALl IALl (iIAL "2,)²²
(R(A.j,) IARl (YZAR VIA
We have following identity regarding the impurity decrease each split.
Lemma A.3 For any rectangle A A. [p) and b IR, it holds
A(A,j.b) = (A(A,,))) + A ((A,j,b) = (A(A,. A
(25)

---

Proef. We just present the proof of the second equality. The proof of the first equality can be proved similarly. Note that
((),j
Σ
(yt DIA) 12-
Σ (v -IAAA )²
Σ (2)
DEAR )²
11
KEZA
72
LETAL
SETAR
(26)
1
(vi DzZ)² (v= DIAL )²]
+ 1
UZAR )a] (vi (zI,)² -w0- -
VEZAL
SETAR
For the first term, we have
1
Σ
(y: FI )2 (ye- - BIAL!" 1²1
n VEIA2.
Σ
(y: Vz - (y: -VIAA) 2( 2I (IZA DIAL ) (MIA - UIAL y²] (27)
n VELAI.
[TAL| (EIA - JIA,)) )²= -A((A,j,b)
Similarly, we have
Σ
[w yI (yr
HEAR) 1²1 = AA((A,.b)
(28)
VETARR
The proof is complete by combining
26 and
28
Lemma A.4 Suppose Assumption
2.1 holds tree. Given a constant a > 0. Given any E (0, suppose
(6/36) < 3/4. Then with probability at least
6, it holds
A(A,j.) b) & (1 a)) + (1 1/a) 50000/2((/36) V Ap.d-1, j. (bl, BER
(29)
and
((A,1,b) S (1+0))(A, + (1 + 1/a) ((000/+(6/36) AA Ap.d-1, j j beR
(30)
Proof. For E Ap.-1, j [p] and a R. by Lemma A.3 we have
(AA,jbb) = (A.
A. b) + An(A,..b)
(31)
((A,j,b) (z - 5.
Define the events & and Ex:
E =
/ FIX E AX E A) SIA I 200 ((6/36)
AEAp.
&
VPX E A)
Inl/n (
ACAp.a
Then by Lemmas A. and A.2
have P(E.) 1- 5/3 for 1, 2, so we have P(n2_,.)) 2 6. Below
we prove (29) and 330 conditioned on the events E and Ez.
Note that
VAI(A,1.)) VF(X AL) AL) A) EXF AL)
S SPIX B(F(XXXX A) SEA + VPIX AL) AL) DIA DeAL
(32)
+ -P(C E Ac)
ÚIAL -XFF(X)IX Ab))
== J. + J2
To bound Jz, we have
JIS VPX B( A) TZA S 200 SOUNtH (((636))
(33)
where the second inequality by event E.. Similarly, to bound Js. we have
Ja = =PXP E AE) UIA, (XF Ac) s 20U 20200O0////00 /f(8/36)
(34)
12

---

To bound J2, note that
J2 E VP(X E At) V /IIa 1/ng 1uzz SIA, + / /Iazl// 18KA - HIAL
(35)
S 5v 2U + V [IAel/n 1NIA yI
where the second inequality made of the event E2. Combining
32
35
have
v (A....)))) s 400 / ((6833)) 10U 10U (((8/12)
IAul/n lūza STAL
S 500 vt(5/33) + /IZzl// 10E - DiAL
which implies (by Young's s inequality)
[TAL
(A & 25500 +
MIA HIAL
(36)
By similar argument, we have
+11+00 a)) [ARl TJT.
AR(A,j.a) (1 11+1/a). 25000/2((6/3))
TJTA
(37)
Summing up 36 and and by (11 have
(A) < (1 + 1/a) 50000 + (1 + a
This completes proof of The proof of 30) by similar argument.
Lemma A.4 provides upper bounds between b)) and ((4, b), which serves as link to translate the population impurity decrease sample impurity decrease. With all these technical lemmas hand, ready present the proof Theorem as shown the next subsection.
A.3 Completing the proof of Theorem 2.3
Define events
& sup /P(X E A) B( A) 8z,1 s 200 (165/24)
AEApu
& = A(A.J.a) s (1+ ( (1+1/0) 50000)
A E Ap Ap.d-1, j (p), a E RR lpl, a E (0/72) < 3/4, so we have 6. In the following, we prove
a) (1+0)
1//o) 550000
AA Ap. Ap.d-1;1
Then by Lemmas A. and A.4 and note that from the statement of Theorem 2.3
P(E)) 2 1 6/2 and P(22 U& 2 6/2, which implies P(U, &,) 2
10 using deterministic argument conditioned on 1
For any &: E [d] and any leave node L of f( (recall that 700) is the decision tree by CART with depth k), let (k) be the corresponding cube, that is, for any æ E R., x E AA if and only if x routed to / in f()) Let
(1) be the set all leave nodes f(h), Then we have
((0) = Σ Tz a00 (2EA!")
(38)
(Ec(A)
Define function
(x) Σ [(( - LEC(N
(39)
where XT the set of iid random variables (x1, (x1, J. and X is random variable having the same distribution in but independent of XT. In other words, ( is with the same splitting structure T(0 and replaces the prediction value cach leave node the populational conditional mean of f-)..
First, using Cauchy- Sehcha- inequality, we have
(1ا - 12 & 2|1 - 1 2115(4) 12 2k) + 2J2(k)
(40)
To bound J: (d), we derive recursive inequalities between Ju (k:) and J1 (k + for a S k < d 1. Note that
(1k =B (x) 7T0) (X)) (T))
Σ P(X E Ar1xT) Varlf Ac,
(41)
(EC
13

---

For each L E _(4), let ir. and Le be the two children of I. then we have
P(( Acl27)) Var(f (T,
= PP E ArL (4)) (ar(f"(X)|X E 21) + +P(X E AER (2T) (x)(x E Acg:21)
(42)
+ 3c,b.
where
(3e, be) E argmax (,)
sElp
Let us define
(Jc.b)) be) E argmax b,) JElrlMER
Then have
b() 2 ++a A(A,,3,, b.) (1000/00
(A,, bb) (5000/0)07+(6172)
(43)
1+a
(1+ A(A,,. b.) 2+ ((0077
a)
where the first inequality is by event Ea, the second inequality is by the definition of (Ge, bz), and the third incquality is because event E2. By Assumption 2.2 we have
A(Ae. b.)
sup
A(Ar.j,b) N P.P(X E Var A.,
(44)
JE(D),ER
Combining 42 and (44) we have
P(X Acc 229)
Var(f"(X)I E A + P Ara (27") Var(ff E Acgi X9))
$ (1 - (1 a1 P(X E A.l (ar(f E 2T)
+ 2+ a ((872) a<1 +
Summing up the inequality above for all E C(K), we have
JA 1) S (1 (1+ + a)2
[1k + 2 2 5(007)
a(1 + a)
Using the incquality above recursively for h 0, 0,1, d - 1, we have
[1(() S (1 (1+a)) J2(0) + a(1
2+a
50000 50000'7(6/ (T(6/22)
Σ 2
k=1
(45)
< (1 (1 + a)3
(X)( +
2+a 50000'7(8/72) a(1 ax)
To bound J2(d), we have
(z(d) =
Σ P(X E (E) E Xt, -Mim.) lEc(d)
(46)
2 2.404000"00000 4(0022 ((5/41)
where the incquality made use event Ex.
Using
and and recalling 40
we have
f( - f 1axx I 22(1-
A
(X)( 20t1. 2 ((0077
(1+
a(1 +
2d41. 44004
2+a (dlog((p)) log(1/0)) 12 (47)
S Var(f A/(1 a) + a(1 a))
2d (dlog(np)) + log(1/))) 12
$ Var(f((X) (1 -1 1/(1 (1
an
This completes the proof of have
10) To prove 11 by taking a 1/d and d= [log(()/ (n) loga A))], we
(1 (1tpp) = (1 1)) 1+
1- (1 (1+))=))) a
(48)
À 2/d 1/df 1
= = =(1 -1- (1 - (1///)
SA (1 x)d
1/d73
14

---

Note that for = (ogg(w))(1 ( - 2)) we have (1 [1* = ///,, hence by taking d' = [logy (n)/(L
logg(1 *])]. have
2d S 2n 14 1-102(1--3] 2n -((A)
(49)
Combining
48 and 49 and note that V - M < U, we have
f 8)
( SA.U n -0() (d log(mp) + d log(1/6))
Sau n -00 (log log(np) log(n) log(1/6))
completes proof [II
A.4 Proof of Lemma A.1
The main idea of proving Lemma A.I is find proper finite net set Ap,ds control the gap on net, and finally prove the result for all A E Ap.a hased on the approximation gap of the net. We need a few auxiliary results. Let S = (0, 1/,, 2/n, ... (n 1)/n, 1}, and define
Ap.d
I [G, Ab.a ui E E for all j [p]
For any A = 1T us] Ap.d, define
A' (IG
where Eg = max {s E S| S Cj},
and u/ == min (s E S| 2 uz}. Roughly speaking, A' the smallest
box with edges in S that contains For any À 18 ūز] Ap.a with ū, Eg 2 2/n for all E [p]. define
B(A)=
I & (1/n)
ūy - (1/n) 160,
and define Bp.d be the of all such sets, that
Bp.
B(A) Ā I1 ūz] Ap.a with üj - i, 2 2/n
The following lemma can be casily verified from the definitions of Ap.s and Bp.d.
Lemma A.5 (1) For any Ap,d, there exists B Bp.d such that A' A B.
(2) P(X B) s 20d/n n for all B Bp,d.
(3) The cardinality
BB.al < AAp.al (2 1)ad <n +n
Finally, for any 2 0, we define
Ap.a(t) A And P(X F(XEA)S()) and Āp.((t)= {A And p(X A) s)
Lemma A.6 Suppose Assumption 2.7 holds true. Let El,.., In be i..dd. bounded random variables with |aa < V almost surely. Assume that for each [n], independent of casiiti but may be dependent on Te. Given any (0, 1), with probability least holds
Σ alMA)) E(ZIL(MEA)) s 2V VT((6)
max ACA (p VP(X E A)
where U M m.
Proof. For each fixed A And \ (p,e(F( that
(((2)1())))) - E(21 E(21 (((A))()))))) ((2))+(X A) 2k22
15

---

so by Lemma
D.1 with = = 2V VP(C A)v = (2V) E A) and = 2V, we have
IP
2 (a,E)) 1(21 > 2V (i(())))
VP(XX E A)
[VVP(XX E A)L(0)
2V VPX E A)L((O)
exxp
4V2P(X A)
2V
(-" = =6/(p'(n 1)2a1
2 eexp
where (1) is because P(X E A) (1) (since A E Apd \ (f) As result, we have
P
aLMEE) - - -((r)( 2V v((0)
VP(X E A)
1=1
Σ
P
(LNEA) ((E) > 2V 21(())
PP(X E A)
A
((
1=1
s App (T,
6/(p"(n + 1)
where the last incquality makes use Lemma A.5 A.5 3).
Lemma A.7 a finite collection of measurable subsets of [0, 1]" satisfying P(X E D) S a for all D E 'D (for some constant ā E (0, 1)). Given any ó E (0, if
w( 6) = (e²x) v log([Dl/2 S 3/4
n
then with probability least 8 holds
lmiee } I w(a.
DED
1=1
Proof. For any fixed D D. denote
P(X D), then by Lemma D.2 for any (0, 3/1 we have
(cEED) > >)) s exp
(log(t//)) (1 f) log 1 1-t
I exp
(tlog(t/a)
log(1 1)))
s exp
(-n (rlog(t/a) (1 - t)(-t) - t1))
exp
(-n (tlog(t//a) 1) +*))
< exp
nt (log(t/a)- 1)) 1))
where the third inequality makes of Lemma that
D.3 and the assumption 3/4. Take t w(ā, 8), and note
log(w(a, 2 log(w(a,
log(e?) 1
we have
L(,,B)) > o( < exp exp (-nw(a, a 8)) < (
where the last inequality is because of the definition of w(ā 8). Taking the union bound we have
LcneDD f> uu(a,)) [D] 5/|D] =
P maxx
DED
Corollary A.8 Under Assumption 2.1 and given 8 E (0, 1). suppose tz(8) < 3/4, then with probabiliiy at least 1 8, it holds
max BEB
Σ
[mEn
< f2(6)
16

---

Proof. Apply Lemma A.7 with D Bydd and a 20d/n. and note that [By,al & (n + 1)2 (by Lemma A.S 2002d (o (8)
(3)) and the definition (6)
Lemma A.9 Suppose Assumption 2.1 holds true. Let 21,...y Zn be i.i.d. bounded random variables with [Z] S V < do almost surely. Assume that for each i [n], z, is independent of { but may dependent on Zt. Given any E (0, 1), suppose tx(8/2) < 3/4, then with probability at least 1 6, it holds
sup AEA (( VP(X A)
1
Σ 2 (mie) - [B(1 (((21))) S5V
(50)
Proof. Define events & and E2:
E1 =
max
(m s (8/22)
REBp,
&2
max Apalt VP(X A)
1
2 (a,EA) ( Vv/1(//2) Σ 1=1
n
Then by Lemma A.6 and Corollary A.8 we have P(Ei) 2 - 6/2 and ((E)) 2 6/2, hence P( (2)) 2 1 Below we prove that when &i and & hold true, inequality (50) holds true.
Note that for any A E An. \ ( (1(8/2)).
1 VP(x A)
2 (ayEa)
E((2 1 (m)a))
Σ
a (1GEA) - Σ 2 (msen))
$ VP(XEA) A) A)
(51)
21 (ayea) E(
(P(XEA)
+ 1
B(al(z)aa)) - B(214(1144))
/P(X A)
= Ti + T2 T3
bound Ti, we have
2 Σ (mnerr))
Ti
(Z
VP A)
VF(X E A)
(52)
V
V
T2(6/2) S Vvl((6/2)
VP(X E A)
BEB
VP(X A)
where the second inequality makes of Lemma A.5 (1), and the third inequality is E1. To bound T2, note that
P(XEA) Ts
1 P(X E A) VP(X E AT)
Σ
2 ala B(al
n
(53)
P(X A!)
2V (h(6/2)
P(X E A)
where the inequality is by event Eg and hecause A' E Ap.a and P(X E A') 2 P(X e A) ((8/2) 2 (6/2).
Note that
F(X E A' A) 2dd
(6/22) SP(X
(54)
where the first incquality by Lemma third incquality is because Ap.a (f, As a result of 53 and we have
A.5 (2); the second incquality the definition of f2(6/2)
the
P(X A' 4) P(X E EA) 2V (1 2 (7(6/2)
T3 5
(55)
P(X E A)
17

---

To bound T3. note that
T3 1
((aal 2 P( E A)
P(X A') AA)
F(X A)
(56)
S V VVP(X A) & V 20d/n S (2
The proof is complete by combining inequalities 51
and (6). and note that
2V f2(0/2) + 2V (6/22) 5V ((6/2).
Now ready wrap up the proof of Lemmal A.I
Completing the proof of Lemma A.1
Define events & and &x:
E1
sup A... /P(X E A)
(2EEA) PP E A) s 55v1(518)
82
sup AEAp (1.611))))) pP(X E A)
ye (m)e) ((y1l(mE)) 50 v((/8)
Then by Lemma
A.9 with and respectively, we know that P(E,) 2 1 8/4 for all i = 1, So
we know P(n 8 1 5. Below prove that inequality (23 is true when 1 hold.
Define (6/8) Then holds
sup AEAp,((o)
VP(X A) A) UIA
(57)
On other hand, any E Ap.d \ Ap,(a), by event ε,, we have
1 (( 2 (z,EA) P(X E A) -1:.:)5555(011 5//88/8 P(
(58)
where the second inequality is because P(X A) 2 100t(8/8). Therefore know E ((CEA) and we can write
E(ynL(z)EA)
Σ Mil(a
E(F" (X)X E A) ÚIA
P(X A)
Σd ((aEd))
B(yll(mEA))
1
Σ v (MEa))
P(XEA) A)
(59)
Wi
Σ ((yEa) - PPX - A))
Σ P(XE))
= (A) + (2((A)
By event &g, and note that a 2 ((5/8), we have
sup
VF(X A)[Hi(A) S 5U 516/1)))
(60)
By event ε,, and note that a 2 E(5/8), we have
sup AcAp Ap.ala)
VF(X A)) 50 (16/8)
(61)
Combining 60 and 61 we have
(((( VP(X A) E A) UZA $ 100 /10/8)
sup
AEAp. (a)
Combining the inequality above with we
VP x A) TZA 200 20U (16/88) S 20U ((8/112
sup
AEAp.
18

---

A.5 Proof of Lemma A.2
Define = 1(6/1) and b =
26d
Define events &₁ and Eg:
(mte)) & (e v log(2(n + 1 1)28p11))
E =
max
ab)) 7
n
1 Σ (z,Ea) S 55v2(8/1 P(X E A)
82 =
sup ACAp a..An.AAp..a (p) /P(X E A)
11
Then by Lemmas
A.7
and A.9
know that P(EI) 2 8/2 and P((2) 2 1
8/2,
8.
Below we prove
24 when &1 E2 holds.
For A E Ap.d. if ifX E A) S then F(4) S a
28d = b. So we have
Σ
1 Σ (mEc)
sup
(MEA) v sup
(mEE)) I sup
x=1
AeAp,ala)
1=1
AEAp.a(0) n1 1=1
1og(2(n + p"""""18))
(62)
$ (eT 2ddm/)) V
< (c2 + 1)1(6/4) < 25((8/4)
where the third inequality is by event & and the definition of b; the fourth inequality is because
T(0/4) 2 (18/4) 2 log(2p"(n + 18) and 1(6/4) 2 (2(6/4) 2 2e 2e'0d/ 0d/n.
As result, have
1
sup AEAp.a(a)
(msEA)
n
(63)
sup (a)
max
VP(X E A),
Σ
(ZLEE))
$5v1(6/4)
where the second incquality made use 62) On other hand,
1 (ayEA)
sup ACAp.i'Ap.lle
VP(X E A)
P(X A)
E 1mse
(64)
sup A
VP A)+
E.= D (x
P(X E A)
(mee)) 55/((1/4)
sup Appa.))Ap.ala)
VP(XX A)
where the last incquality event E2. Combining
63 and
64 the proof complete.
B Proofs in Section
For any interval E E E and any univariate function on |0, 1]. let VB) be the total variation of g on E. For the additive model (14) and rectangle A = I1 E, E A. define Vy-(A) Σラ= Vyz (E,). Recall that X a random variable with the same distribution as æ, and (i) is the j j-th coordinate of X.
B.1 Technical lemmas
Lemma B.1 For any rectangle A S [0, 1]P any [p] and any b IR, it holds
A( = [E(S [EI (X](X E A)P(X E An))
P(X E A)
P(X E Ax) E Ar)
where At b) and An An(i.).
19

---

Proef. We use the notations v := (X/ E = -()(=))( E Ar) and PR = E(M(X)
AR). First, note that
- I (() (X(A))))) = (x) V tuz - 11)11
(65)
= E (X) - (2)(I(XEA)) + (uz -U) At)
Similarly, we have
E ((f w) (1((x)m))))))
B ((f PR) PR) ((XEAN)) + (VR- - -) AR)
(66)
Summing up 65 and (66) we have
(vr. - P) E (VR -)) (UR
E AR) - (()(((x))(((xxx)) - (()
(1)E((XEAL)) - (U - uR) (67)
=
= ()).j.)
Note that
(vr. V)PP-) E = (BU((X))(XXA)) -PP( E An)) (P(X (PCX E Ar.)
(MMMX E A) -B( (X)((X)XXXXX UPP(X E AL)) ? (F(X E AL)))
(68)
=(UP(X E An) (X(((X))(NEAA)) (P(XE AL))
=VR w)² (P(X AR))²
P(X E AL)
Combining 67 and 688 we have
b) (VR w)² (P(X E An))² + (VR v) E AR) (VR (1)=-))= P(X E AR)P(X A)
P(X E Ar.)
P(X AL)
((((()))))XA))) vF E AR))
A(
P(X A,) E AR)
Lemma B,2 Suppoxe Assumption 2.1 holds true, and f has the additive structure in 14 Then for any A = 14, ugl S [0, 1IP, it holds
F(X E ()V)( E A)
A(A.j.b)
JE HER
Ei Se V (t)( - LA (t))dV;;
where (1): : (4) S t/ E A).
Prouf. For fixed A 16 uy] S [0, II", without loss of generality, assume EX(((X) E A) 0.
Note that for any E [p).
QA (s)(1- - A(A, ()) 1 (s)( - (5)) (s)) 1V ((),,))
dV,; (1G),
max BER
((A,).8)
(69)
where s the integration variable. Because AA that we have assumed [X) E A) = 0, we have
( (s) = P(X E AL(;,)))/P(X E A), using Lemma B.1 and recall
2 (s) () dV ())
((F(())(XEANNG)))) (V5)((es,))) s))
VP(XEA)
(xx( dV s))
VP(XEA)
2 VP(XEA)
(Ue( dff (s)
VP(XE
B(((())
L(xeat)
VV(XEEA)
20

---

where the last equality makes use of the assumption that ((M E A) 0. Combining the inequality above with (69). we have
max
VP(X St, (s)( dV ((6,,)) V A(A,1,0)
DER
As a result, we have
ΣE=1 B(F (x)
max JEIR
VA(A,J,b)
(70)
vP(X E A) Eド= Sey ( 2 (6)) dV (1e,s))
By the additive structure 14 we have
2 B((((()) - P(X A] A)
(71)
Combining (70) and 71). the proof is complete.
Lemma B.3 Suppose Assumption 2. holds true, and f has the additive structure in 14 If for any A
I1 (2,, uy] S [0, 1)2 and any lo Ip. it holds
S
Vo (3) (1) (1) (t)) aV (1)=
7²
inf L/d wER
(2(() w/ dt
(72)
uh la
Then Assumption 2.2 satisfied with x 0/ Op)
Proof. Given A 11 1e,, uz] [0, IJ". without loss of generality, assume (X E A) O. Let
px (-) be the density of X on [0, 1JP. Then we have
((( P(X E A) J (3))) dz (73)
0
Var(f*())IX E A) P(X E A)
where the second inequality made use of Assumption 2.1 (t). Denote Cj == wy-Tr Siy (1)dt and c
2 Cj. then have
((( de (/(ttt///tt
(c+
Σ f1(z)) - .)² "2i ... dip
1
/ ج [(s())) -c,)² d2idzz dzp
5=1
IP (ux -(x) 1Th (17(1) - c,,)² de
U -by
1=1
P(X E A)
1 (") (1)(t) - -,,² dt
Ug l, [1
Combining the inequality above with have
0
25 (d -,)())
Var(f" E A)
(74)
Uy e, J13
We use H& to denote the LHS 72 then 72) implies
t E, I. (5(()) - c1 di 2 H3
1
(75)
As a result of
74 and 75 we have
Var(f"(X)(XE A) 0 2 0-2 Σ Hi
(76)
21

---

By Lemma B. we have
P(X E (XX E A)²
max A(A,i.) JEPI
(h Hc)²
EE=1 H
P(X E A]Var( A)
27
(E Ha)²
0
2
P(X E ()
p072
where the second inequality is by (7). and the last inequality made use of the Stuchy-Schwarz inequality.
B.2 Proof of Proposition 3.1
For any A 11--1 (c,, us] S (0, 1)" and any l E (p) holds
S.
V (2) (0a (1)) a (14x, (1)= S 3 ([((1110010
102)(0) a)²
72/4 Uk la
$
inf
J. (f2 - w//2 dt
WER
where the first incquality is by Cauchy-Schward incquality, and the second is because fū E (),
Using Lemma B.3 the proof of complete.
B.3 Proof of Proposition 3.2
For any A 16 uz] S [0, 1|" and any E [p], we prove that
S"" (f (011 (1) a (().. & max {
2nd x2
max + +
inf ["
n"k
[ de
20
ux lu
weR
(77)
Then the conclusion follows Lemma B3
For fixed A and & E [p), simplify the notation, we denote fū, a: le, b = uk ((1) = -/24 (f) for all
t [ex, un), and = t3 for 0, l,..,,,. Then (77 can be written as
S.. Va(t)(1 - (()) dV dV 2r max ( Ø r max (93?,32 max
828
inf L (o(t) w)² dt (78)
0 4a
b-a
For any E (0, define Ag(s) = lim g(t) - lim g(t). J' E [r] such that f S < <ty and 11-11 < b tym,, and detine r' = =j" - + and
20 = a, 21 = tgr, 22 ty44s ..., Ep 1y F,r =,r= b.
Then we have
S vo(1)(1- o(0) (l5)
V000(1-- 9(0)1 (1) di +
qq(z))(1 ((3))))o())))
(79)
1-1
24' Σ
(1) dt) + 2(r - 1) Σ (1 - g1)))
We have the following 4 claims bounding the terms in the last line of the display above.
Claim B.4 For j E (1,7',, holds
S Va(t)( -(())1((())00())
032
inf (
<
(o(t) w)
0(b a)
weR. 2,-1
22

---

Proef of Claim B.4 We just prove the claim for j = 1. The proof for j = r' follows a similar argument. To prove the claim for 1. we discuss cases.
(Case 1) ((11) & 1/2. Then we have vq(0( - a(()) & vi(zz)( ((1)). hence
SL Vi(t((1 (0000100)))(00)) dt) s -(())((1((aa))
L. 9 (((t)
$²
1- (o(1) w)
$ {0(a1 g(21))
inf
(80)
WER
0
inf
(g(1) Rf
0b
WER
where the second inequality is because LRP( 21), B): and the last inequality makes use of the fact ((=1) I 0(21 a@((@(b a))).
(Case 2) ((11) 1/2. Then we have
aa [(b ((11)
@(b a)
(81)
20
As result,
1 S.. (000110000000 du)² $ 1 f (1) 1 4(21 - a) weR
13
inf ['
(o(1) w)2 de
033
/-" (9(1) - w) dt
inf WER
20 a)
where the first inequality by Cauchy-Schwarz inequality; the second inequality because g LRP((a, 21), B); the third inequality is by (8I).
Combining (Caes 1) and (Case 2), the proof of Claim B.4 is complete.
Claim B.5 For j E (1,7' - 1}, it holds
40 r max (
max
4} inf WEB
52 (9(1) w)? dt
- ((=(1=
Proof of Claim B.5
just prove the claim for j The proof r' follows a similar argument. To
prove the claim for j 1. we discuss two cases.
(Case 1) [2(a))
max Ig (1)) dt, J Ig (t) dt). Then by Lemma D.6
we have
inf ( (o(1) w)? dt 2 min {=1 20. 21 (a)(2)))
(82)
16
Note that
min {21 22 }1} min 0q(21)
a) min { 09(21)
- (b-
(b-
(83)
So by
82 and 8 we have
Ø
r 16 inf
/" (g(() - w)² dl
Ag(=))) & max
0g(2))'
a
a
WER
20
As a result,
q(=1((1 ((E:)))
max { 4(21)), -
-(21))) a
16
inf
32 ('(((() (a(1) w)² dt
wER
(Ø) Aa b WER I" (o(t) - w)
( rl 16
$ max
where the second inequality by Cauchy- Schwarz inequality.
(Case 2) [ < 4 maxx Is (V) dt f Ig (4) di). Then we have
(1=)(11 (( 4g(2)) ((>1)) max {/ (e'()) / ae()))
(84)
23

---

By the same argument in 80 we have
-(()))(1-((t)) 1s (()
483²
inf [" (x(() "
(85)
B(b a) wez
On the other hand,
4g(21) (1 g(211) (11 (0(t)) at) (t(t))at)
(f5 (t))
(86)
1" (Ø(t) - w)² dt a(b a) inf
r33
[" (g(t) - w)
inf
22 WER
WER
where the second inequality is because E IRP(((21, #2), B); the last inequality is hecause 22 a/r
(a/r)(b 106--00 a). By 184 85 and (86). we have
- -
max
40
r
8
inf WER
52 (g(1) w²) dt
0
Combining (Case 1) and (Case the proof of Claim B.5 is complete.
Claim B.6 For 22/SS - holds
rg² J (((0)( dt)² s
inf f (o(t) - d
4a weB 2j 1
Proof of Claim B.6 Note that
(L
B²
inf (o(t) dd
1(2g 2)-1) wER 25-1
r inf WER J,
(g(t) d)
4a a)
where the first inequality is by Cauchy-Schwarz inequality; the second inequality is because g LRP((2)-1; 2y), the last inequality by the assumption that t, - ty-1 2 a/r.
Claim B.7 For 2 2SiSr 2, holds
a(2;)(1 - ((s))) 1max(33,4)
511 (g(1) - w)² dt
inf WE
53-1
Proof of Claim B.7
We discuss cases.
(Case 1) [A]()))
maxx (t) Jt, (31 [t) dt). Then Lemma D.6 we have
(g(1) w)2 di min {2, 25-1, =,) (Ag(ε,)) ))
(Ao(z;))²
inf mER
16
16
As a result,
16r
[ (9(() - w)² de
((=) = a
(12;)( - g(2;))
inf
WER
55-1
22 (g(t) w) dt
inf
2/-1

---

(Case 2) AAm())) - 4 1 4maxx (g' di -- S (g) di). Then we have
((=;)(1 ((2)))
Id(()) dt, 1o 9 d(())
$ <4g(z)) ((2))) max
s max
[s((t) dt,
de()))
< max
g²
inf
(o(t) ww)² dt,
inf
(
(0(1) w))² dt}
2--1
WER
25+1
wER
8r
[
max
inf WEB
(o(() w) dt, inf
(9(1) w) de
[+]+] (o(t) - w)² dt
inf WER
where the sccond incquality is by Cauchy-Sehward incquality; the third incquality is because g 2))(( B) and g LRP((2;, 2j+1). B).
Combining (Case 1) and (Case 2), and note that b S 1, the proof of Claim B.7 is complete.
Completing the proof of Proposition 3.2
By 79 and note that r' I r. we have
(
(0)(1 (()) (V)
(87)
2r
Vi(0(1- (006s(())))))))) +r Σ -(s))(--(z -0())))
j=1
By Claims B.4 and
B.6
we have
Σ (00)(11(())l)))) (0)
5-1
max
0
r.3
Σ
inf
1" (9(1) w)
(88)
[(b a)" 4a
j=1
4--1
0 r
8²
/" (9(() =w)
max
10'4a da b
weR
inf
By Claims B.5 and
B.7
have
(12)(11 (1=)(119(2))) 9(2))))
max { 40 r max 12 ,4
inf (*)+) (g(t) w)²² dt
( @
1=1
2j-1
(89)
{ 10 r max 18
inf /' (g(t) w)² dt
max
0 a b
WER
max {0 r
max
32)
inf
(g(t) - w)²
WER
By 87
88 and 89
we have
S. (((0)( - 9(t) dv, dV, 11))
max (982 32 82) 1o 4a b b-a a
inf f (g(t) - w)² dt
< 2r max
wea
Hence 78 is true, and the proof of Proposition 3.2 complete.
25

---

B.4 Proof of Example 3.1
Given (a. 6] - [0, 1]. without loss of generality, assume f g 0 (because the infimum in w achieved at
La g(t)). Let to E [a, 6J be the point with g(ta) = 0. Since g (t) 2 > 0, we have
| (o(t))
dt [ (a - to)) (ci(t-
dt = ci (b to)
Similarly,
J. to (o(1))) dt dt> ("(a (ai - -))3 dt
c (to
a)
3
As a result, we have
[(0(0)) de o (b- (b- to) (to - -n)²)
2c
b a
c
(
a)²
(90)
3
2
12
On the other hand, since Ig' (t) S cz, have
s oz((b (o)))))))))))))
a)²
(91)
Combining
900 and 91
we have
( (0 dt)
c: a) J. (o())) de
12c3
B.5 Proof of Example 3.3
It suffices to prove that there exists constant C, such that for any univariate polynomial with degree at most and for any a < b.
Cr (s(()) du) - bb- 1o(())
(92)
We first prove the conclusion when 0 and 6 1. Let P(r) be the set of all univariate polynomials with degree at most Note that P(r) is a finite-timensional linear space, and the differential operator 4 g + g is linear mapping on P(r). As result, there exists C, such that
[ 10'(t) dt s vc. sv. 1/" lo(t))
for all g E P(r).
For general a < b, given E P(r), define h(s) = g(a + (b - a)s), then E P(r). So we have
J [s)) ds S vC. //'' [h(s)] ds
(93)
Note that
[." I (s)) ds (b (b-a) S' lg' + (b a)s) do = [ (g(()) de
(94)
and
[ [n(s)) ds J.'' I9(a+ + (b (b-a)s) ds b- f le())d de
(95)
Combining 93
94 and 95
we know that
Cr a'))))) /Cr f. l9(t)) at) b-a L. lo(t) d
where the last step by Cauchy-Schwarz inequality.
B.6 Proof of Example 3.2
It suffices to prove that for any o, b E [0, 1] with a < b, it holds
[ (o)( dt 110(L/o)
L. la(t)) de
(96)
b
Once 96 is proved, the conclusion is true via Jensen's inequality.
26

---

Below prove (66) Denote C' = 1/10. For given a, b E [0, 1]. without loss of generality, we assume the median of on (a, bj is O, ie.. Sa (( = [- 1 oo = (b - a) 2 (otherwise translate by constant).
We discuss two different cases. We denote m := min (#)) and == maxig(u.0) Olg' (t]l}-
(Case 1) m 2 C(b - a). Since g I-smooth on [0. 1]. we have
M S m + L(b - a)
Hence we have
M
L(b L(b-a) a) S <1+1/C L/C
(97)
where the second inequality is by the assumption of (Case 1). Since mitteeje. (1)1(())) = m O. without loss of generality, we assume that (t) > 0 for all t E [a. b]. Denote to = (a + b)/2 By our assumption that the median of on (a, b] is O, we know that g(to) = 0. Since is convex, for any E [a, to]. we have
g(ta) (t) to
(g(to) g(a))
which implies g() S to ( g(to)) - 0. As result, we have
[ø(t)| dt 2 (t() g(a)و ta (fo a)²
2 m
m
(98)
2
8
On the other hand,
J_ (9)( di S Mb a)
(99)
Combining 98 and 99 we have
8M
m f (9(1) at S 8(1 + L/C) S 19(1) di = 88 1 (s(0) de
(b a)
of (1)
de
where the second incquality made of (Case 2) C(b a). Then by the T-smoothness of g we have
M (C L) - a)
so we have
f. (t)(t) dt < M(b s (C L)(b-a))
(100)
Define interval [81, == {t E (a, b] (() S 0}. By our assumption that the median of g on [0, 1] is 0, we
have 12 - 11 = (bb =bb-a/²² Denote to = argmin g(t). Define function f on [f1;
((L) = g((n) (t 41)/(lo -4) tt) LE [o] g(ln) (l2 - 1)/(12 - ()) LE [L. L2]
Then 0 2 *()) 2 st) for all t E [t1, [2] (because g is convex). Note that
1" f(t) df (o( t1) go(to)((z to) -0(t))(22- - -t1) -11)= S,¹
1
(n a(to) dt (101)
As a result,
(a(t) dt 2 1, 8 [(t) dt -- d 1, f(t) dt 1"h
n f(t) g(to) dt 2 f g(t) ((o) dt (102)
b,
where the first and last inequalities are because 0 2 f(1) 2 s({) for all E [/1, L2]; the second equality is by
TOT. Note that for any [fa,ta]. tz).
g(t) ((t) 2 ((o)) 10) + ? (o) ク (o)
(103)
where the first incquality is because is a -tstottly-cooveett and the second is because to is the minimizer of on [t1, f2]. By (102) and [03). we have
L. (o(t)) di
(12 1//22
10)² di 2 J.
5² dt (12 t1)²
192 (b a)*
Since g is convex on (a, b), the median of on (a, b) is O. and [ti, t2] = {t E [a, 19()) s 0), it is not hard to check that
(o()) dt 2 1 lg(t)) dt
(b a)a
(104)
96
Combining (1O0) and
104 have
96(C + L)
J' (o(t) dt < 110(L/o) 1" lø(t)) dt
lo'(t) b b-a
where the last inequality made of C' L/10. The proof complete by combining the discussions in (Case 1) and (Case 2).
27

---

C Comparison of Theorem 2.3 and Theorem of [10]
We first restate Theorem of 10 in the setting of fitring single tree (note that 100 discussed random forest).
Proposition C.1 (Theorem of (T0) Suppose Assumptions 2.2 and 2.1 hold true. Let (.) be the tree 1/8, 0 < c < 1/4 and > with 21j < 8 1/4. Then there existy constant C > O such that for all n and d satisfying S d I e clog2(n) it holds
estimated by CART with depth d. Fixed constants an > 1. << <
B(Il - ( S c("
(n"" " (1 az 2) +n Sto)
(105)
In particular, the RHS of 105 is lower bounded by
9in
-80 + n (l))g((-1))
(106)
Note that (106) follows (105) by the fact 1 S d S (1ogg(n) and ag > 1. In the original Assumptions of Theorem in 10. it was assumed that the noises can be heavy-tailed, which is a weaker assumption than Assumption 2.1 However, the parameter controlling the tails of the noises did not explicitly enter the error bound 105 and seems that their proof techniques cannot improve the error bound even under the assumption that noises are bounded. In addition, the dependence on p was not explicitly stated in the bound (103), which seems to be hidden in the constant C.
To compare our error bound with the error bound in (06)). since the |1 -f 1" is bounded almost surely, it not hard to transform the high- high-probability bound ①II to an bound expectation, and we have
B(IJ s" (1))) & On -+() log(np) log" (n))
(107)
Below we discuss two different cases.
(Case A 2 1/2. Then holds
1og (1 - A)
(1/2)
<(A) 1 log (1- - X) 2 1- (1/2) 1/2
(108)
our convergence rate 107 O(n 1/2 log(rep) (re)). but the rate (106) is
M(n + n
5tc + n (1)))(11>1) 2 2(n ") 2 2(n 1/88)
(109)
(Case 2) < X 1/2. Then it holds
1 1 log (1 - A) S -
1 (1/2) =
(110)
and hence ((A)= logg(1 2)/2. So our rate in 107 is O(n 1og A3/2 log(mp) log"(())) (m)), but the rate (106) is
A(n " + stc + ne cloo)(1--)) 2 ann cloz 2 12(n logg(1-
(111)
D Auxiliary results
Lemma D.1 (Bernstein's 's inequality) Let Zi....., Za be i..dd random variables satisfying [B((Z)
E(Z))))) (162) for some constants 7, > O and for all k 2 2. Then for any
n (
P z. -
>1) < 2exp
Lemma D.2 (Binomial tail bound) Let 7 . Zo be i.i.d. random variables with P(Z, 1) a and
P(Z. 0) 1 a. Then for any E (0, 1),
S exp -n (log (2) + (1 1) 1-t
P
Lemma D.3 For any & E (0,3/1), log(1 - t) >
-t
Proof. For E (0,3/4).
log(1 - 1) + + f
t2
1
Σ
k
1
>
0.
k!
2
6(1
kmd
km3
28

---

Lemma D.4 Suppose Z is random variable satisfying E(e²2) I ex for all X E R, where > 0 is constant; then
E 211² S 9a*k!
Proef. By Chernoff inequality it holds P(|Z) > () - 2exp( -t/ -P/((22)) for all <> 0. As result,
B(12"1/(klo")) - B(e B(e {- e'P(IZ//a 1) dl
$ 1/- 2exp (1- 5 di 2vē /0" exp(-(1- 1)2 di
2
$ $2ve I expl-t/12 dt 2 5
Lemma D.5 For any integer & 2 it holds t (t11 S (Zमッ5..
Proof. any & 2 holds
(2h: + () + 1)
2 11+ /) (1 1 (1+ )=++)/=2 <2
(1+
2
2k
Multiplying 2/(k 1) in the display above, have
2k 1
1
( - 1)2 <
(k + 1)3
The proof complete by noting (1++1))
22 (1+1)2
Lemma D.6 Let ba be sub-interval of [0, 1), and (a, b). Let h be a function on [a, b] such that h is differentiable (a, c) and (c, b). but be discontinuous at c. Denote Ah(c) lime h(t) si h(t). Suppose
Ah(c) > 4max { [h'(t)] dt, [- (W((t) dt
(112)
Then it holds
WER (1((1) inf J (b(()) - w)² de 2 (ilcca,bbe((MM()))/1
Proof. We assume that is continuous since otherwise, the conclusion holds trivially. We use the notation Mc++ == lim h(t) and h(c-) = lim h(t)- Without loss generality, assume hic+)= > li(c)).
For w 2 (1/2)(((c+) + M)-)), it holds w - -((c-) 2 (1/2)An(c). By 112 we know that for any t (a,c),
(h(1) - h(c-)] [ [V((T) dr & 1 Ab(e)
1
Henee for all t E (a,
1 w h((l) = h(c-)+++ h(--) -4()) 2 マタ Ah(c) _/)(C) 1 AA)())
As result,
[" (h(tt) w)² dt > | (h(t)- dt (c- ()hce()))/1 For (1/2)()((c) h(c-)), similarly, we prove
(113)
[ - w) di w3 (b (0- (A)(e))//)
(114)
The proof complete by combining
113 and 114
29


Reviews:
[{"review_id": "ttLx4eqqb0", "reviewer": "Reviewer_1fUr", "summary": "In this paper, the approximation of the model obtained from the decision tree learning algorithm CART is analyzed. More precisely, in Theorem 2.3, a convergence rate of the decision tree approximation compared to the true model is obtained. This analysis is performed under two assumptions of the paper (already introduced in the literature), with the Sufficient Impurity Decrease (SID) assumption in particular. Finally, examples of true models that satisfy the SID assumption are proven.", "questions": "\nTypos and minor comments:\n- l38: the the -> the\n- l104: Chi et al.[10] -> Chi et al. [10]\n- l144: the notations $\\bar{y}\\_{\\mathcal{I}\\_A}$, $\\bar{y}\\_{\\mathcal{I}\\_{A\\_L}}$ and $\\bar{y}\\_{\\mathcal{I}\\_{A\\_R}}$ are not introduced\n- l163: \"as\" -> \"at\"\n- l193: \"Assumptions‘2.1\" -> \"Assumptions‘ 2.1\"\n- l240/246/247: Poincare -> Poincaré \n- l242: $\\kappa$ -> \"$\\tau$\"\n- l704: there is an indefinite reference \"??\"\n- The references are not \"standardized\", e.g. for JMLR it is written \"The Journal of Machine Learning Research\" or \"Journal of Machine Learning Research\"", "limitations": "The limitation about the the SID condition is discussed in Section 5. Moreover, I do not see any potential negative societal impact of their work.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper is well-written and easy to follow (although I did not check the proofs).\n2. The analysis of Theorem 2.3 improves the result (i.e., the convergence rate) of [10].\n3. Proposition 3.1 links the SID condition and the class of functions satisfying the Locally Reverse Poincaré condition (that is proven for some classes).", "weaknesses": "1. The additive structure assumption of $f^*$ seems restrictive (but is also assumed in previous works). \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your overall positive assessment of our work. \n\n\nReply to weakness 1:\n\nThank you for this comment. Actually, it is possible to relax the additive model on $f^*$ such that it is ``approximately additive\". More precisely, we can assume that there is an additive function $g^*$ that approximates $f^*$, such that in each rectangle A, the L2 distance between $f^*$ and $g^*$ is bounded by a small constant of the variance of $f^*$ on $A$. \n\nOn the other hand, it seems hard to further relax this condition. Consider a two dimensional model $f^*(x_1,x_2)$ with features $X_1$ and $X_2$ independent. Suppose $E(f^*(X_1,X_2)) = 0$.\n    We can decompose $f^*$ into additive components and a remaining term:\n    \\begin{equation}\n    f^*(x_1,x_2) = f_1^*(x_1) + f_2^*(x_2) + h^*(x_1,x_2)\n    \\end{equation}\n\n where $f^*_1(x_1) := E(f^*(X_1,X_2) | X_1=x_1)$, $f^*_2(x_2) := E(f^*(X_1,X_2) | X_2=x_2)$ and $h^*(x_1,x_2) := f^*(x_1,x_2) - f_1^*(x_1) - f_2^*(x_2)$. Then it can be checked that \n    \\begin{equation}\n    E (h^*(X_1,X_2) | X_1) = E (h^*(X_1,X_2) | X_2) = 0\n    \\end{equation}\n\nIf the additive components $f^*_1 + f^*_2$ are small, say, in the extreme case $f^*_1 + f^*_2$ is zero, then $f^* = h^*$, and by the inequality above we know that the SID condition cannot be satisfied. Therefore, for the SID condition to be satisfied, it is necessary that the function $f^*$ has a significant amount of signal that is additive. \n\n But of course, this is for the SID condition to be satisfied. It is possible that CART can still work well without the SID condition, \n    which needs more exploration and is beyond the scope of this work.\n\n\nReply to questions:\n\nThanks! We will correct them in the revision.\n"}, {"review_id": "MLoiCbVggo", "reviewer": "Reviewer_vX7v", "summary": "The paper focuses on the analysis of the prediction error of Classification and Regression Trees (CART) for regression problems under a sufficient impurity decrease (SID) condition. The SID condition is a strong assumption on the approximation power of tree splits, which can ensure the consistency of CART. The paper establishes an upper bound on the prediction error of CART under the SID condition and shows that the error bound is tight up to log factors. The paper also discusses a few sufficient conditions under which an additive model satisfies the SID condition. The paper's first contribution is a refined analysis of CART under the SID condition, which improves upon the known result by providing a tighter error bound. The paper's second contribution is the decoding of the mystery of the SID condition, which builds a connection between the two types of assumptions in the literature: the additive model and the SID condition. The paper discusses a few examples of how the locally reverse Poincare inequality can be verified. Overall, the paper provides a refined analysis of CART under the SID condition and sheds light on the connection between two types of assumptions in the literature: additive model and SID condition.", "questions": "Referred to Strengths and Weaknesses", "limitations": "Referred to Strengths and Weaknesses", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper has several strengths. First, it provides a refined analysis of the prediction error of Classification and Regression Trees (CART) under a sufficient impurity decrease (SID) condition for regression problems. The paper establishes an upper bound on the prediction error of CART under the SID condition and shows that the error bound is tight up to log factors. Second, the paper discusses a few sufficient conditions under which an additive model satisfies the SID condition. Third, the paper provides examples of how the locally reverse Poincare inequality can be verified.", "weaknesses": "I think the work is significant. I don’t have many concerns, but I have some questions about the method.\n1. Can this method be extended to classification problems?\n2. In theorem 2.3, why do you need to suppose n satisfies such a complicated condition?\n3. Also, in theorem 2.3, why should d be fixed to a function of data size? \n4. In line 32, is it [0,1]^p?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your overall positive assessment of our work. \n\nReply to weakness 1:\n\nThanks for this great question. It depends on the specific version of classification trees under discussion and the loss used to make splits and measure the accuracy. If the prediction in each node is the majority votes and the loss is the 0-1 loss, then the current analysis does not apply, because the impurity decrease considered in this paper is specific for square loss. \nIf the prediction in each node is the empirical probability of lying in a class, and the loss is continuous with curvature (e.g. cross-entropy), then it is possible to generalize some of the analysis for classification. \n\nReply to weakness 2:\n\nThanks for this question. The condition on n is needed for some uniform bound between the empirical and population means of some quantities. This condition is mild in this context:\nIf $\\bar{\\theta}$ and $\\delta$ are constants, then this condition only requires that n is large enough with $dlog(np)/n \\le O(1)$. \n\nReply to weakness 3:\n\nThanks for this question. \nNote that the error bound in (10) holds true for an arbitrary value of d, while the error bound in (11) is true only when $d \\sim log_2(n)$. \nWe take $d \\sim log_2(n)$ simply to minimize the RHS of (10) and \narrive at the error bound in (11). \nThis value increases as $n$ increases, because when more data is available, a larger model can be used to decrease the bias without significantly increasing the variance.\n\nReply to weakness 4:\n\nThank you. We will correct it in the revision.\n"}, {"review_id": "G2zfQwvdk1", "reviewer": "Reviewer_MZ6v", "summary": "The paper performs theoretical analysis of the well-known CART algorithm. The authors show a convergence rate of CART under the condition called 'sufficient impurity decrease' (SID), which is tighter than known ones. The authors further provide the condition for a class of functions that satisfies SID.", "questions": "- Is there any insight that can be derived by the proposed analysis for tree ensemble models such as random forest? ", "limitations": "A limitation about lambda is discussed in Section 5.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper seems technically sound and the analysis of CART would be important. \n\n- The paper elaborately explains differences from past work in particular from [10].", "weaknesses": "- Experimental verification is only in one quite simple figure for the simplest case. Of-course, the paper is a theoretical paper, but if richer empirical evidences had been provided, it would have been convincing more (such as different true functions and comparison with past bounds). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your overall positive assessment of our work. \n\nReply to weakness 1:\n\nThank you for this suggestion. The reason that we only did the simulation for linear functions is that for other signal functions, it is hard to precisely evaluate the SID parameter $\\lambda$, hence difficult to set up a fair baseline for numerical evaluation. We would like to do more explorations in this direction in future works. \n\nReply to question 1:\n\nThank you for this question -- it immediately leads to considerations for future works. By a similar argument as in [10], we can immediately derive an error bound for regression random forests. But on the other hand, this error bound is at essence for a single tree and does not make use of the ensemble structure. If the structure of ensembling is properly analyzed, it is possible to derive a stronger error bound than the one given in this paper. "}, {"review_id": "Ng5XFAE9A9", "reviewer": "Reviewer_xrLy", "summary": "The paper studies the convergence rate of CART, a greedy algorithm for building decision trees, under a regression setting. It introduces a sufficient impurity decrease (SID) condition on the underlying function that ensures the consistency and polynomial convergence of CART. It also provides examples and sufficient conditions to verify the SID condition for various function classes, such as additive models, polynomials, and smooth and strongly convex functions. ", "questions": "1.\tDo Examples 3.1 - 3.3 still hold if they are generalized to high-dimensional situations?\n2.\tThe additive model assumption in Section 3 is still quite strong, is it possible to use milder assumptions?\n3.\tThe intuition behind the LRP condition needs further explanation, does this mathematical property have any implications for improving the CART algorithm? Maybe it can help explain why CART tends to handle data with certain structural characteristics.\n", "limitations": "NAN.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe paper provides a refined analysis of CART under the SID condition, which improves the prediction error bound over the previous work by Chi et al. (2022) and shows its optimality up to logarithmic factors.\n2.\tThe paper decodes the mystery of the SID condition by introducing a locally reverse Poincare (LRP) class of univariate functions and showing that additive functions with LRP components satisfy the SID condition. This connects the two types of assumptions in the literature: additive model and SID condition.\n3.\tThe paper demonstrates the practical utility of its results by providing examples and sufficient conditions to check the LRP property for various well-known function classes, such as polynomials, smooth and strongly convex functions, and strongly increasing functions.\n4.\tThe paper is well-written and clear, with detailed proofs and explanations in the appendix. It also includes simulations and figures to illustrate its main findings and compare them with existing results.\n", "weaknesses": "1.\tThe paper relies on some technical assumptions and conditions, such as bounded errors, bounded signal function, and LRP property, which may not hold or be easy to verify for some function classes. It would be helpful to provide more intuition and motivation for these assumptions and conditions, and discuss their implications and limitations for the applicability of the results.\n2.\tThe improvement of the convergence rate in this paper still heavily relies on the SID condition. Although the paper decomposes and illustrates the SID condition with some examples, they are still mathematical forms in 1-dimensional situations. If the paper could further analyze the SID condition in relation to the structure of real data, then its contribution to the SID condition would be more convincing.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your overall positive assessment of our work. \n\nReply to weakness 1:\n\nThank you for this suggestion, we will add a discussion in the revised paper. \n\n\nReply to weakness 2 and question 2:\n\nThank you for this comment. Actually, it is possible to relax the additive model on $f^*$ such that it is ``approximately additive\". More precisely, we can assume that there is an additive function $g^*$ that approximates $f^*$, such that in each rectangle A, the L2 distance between $f^*$ and $g^*$ is bounded by a small constant of the variance of $f^*$ on $A$. \n\nOn the other hand, it seems hard to further relax this condition. Consider a two dimensional model $f^*(x_1,x_2)$ with features $X_1$ and $X_2$ independent. Suppose $E(f^*(X_1,X_2)) = 0$.\n    We can decompose $f^*$ into additive components and a remaining term:\n    \\begin{equation}\n    f^*(x_1,x_2) = f_1^*(x_1) + f_2^*(x_2) + h^*(x_1,x_2)\n    \\end{equation}\n\n where $f^*_1(x_1) := E(f^*(X_1,X_2) | X_1=x_1)$, $f^*_2(x_2) := E(f^*(X_1,X_2) | X_2=x_2)$ and $h^*(x_1,x_2) := f^*(x_1,x_2) - f_1^*(x_1) - f_2^*(x_2)$. Then it can be checked that \n    \\begin{equation}\n    E (h^*(X_1,X_2) | X_1) = E (h^*(X_1,X_2) | X_2) = 0\n    \\end{equation}\n\nIf the additive components $f^*_1 + f^*_2$ are small, say, in the extreme case $f^*_1 + f^*_2$ is zero, then $f^* = h^*$, and by the inequality above we know that the SID condition cannot be satisfied. Therefore, for the SID condition to be satisfied, it is necessary that the function $f^*$ has a significant amount of signal that is additive. \n\n But of course, this is for the SID condition to be satisfied. It is possible that CART can still work well without the SID condition, \n    which needs more exploration and is beyond the scope of this work.\n\n\n\nReply to question 1:\n\nThanks -- these are great questions. We believe that Examples 3.1 and 3.2 still satisfy the SID condition in multi-dimensional settings (for Example 3.1 we assume strict monotonicity in all the dimensions). \nFor Example 3.3 we are not sure, as multi-variate polynomials may have some symmetric structure (like the XOR gate) that makes a single axis-aligned split fail to work. \n\nReply to question 3:\n\nThanks for this helpful comment. LRP condition indicates that CART can handle the signal in which there is a significant local variability (characterized by the derivative). We will add some comments in the revised version."}, {"review_id": "AexaZNKlSi", "reviewer": "Reviewer_te2H", "summary": "This paper improved the rate of consistency of CART based on a sufficient impurity decrease (SID) condition under regression settings. Then, the authors provided examples, which are mostly special additive models, that can satisfy the SID condition, and showed that the rate of consistency cannot be improved by more than a log factor.", "questions": "I would like to ask the authors the following questions:\n\n- Can the SID condition be satisfied in multi-dimensional settings without assuming additive models? See Weaknesses #1.\n- May the curse of dimensionality be avoided when the SID condition verifies? See Weaknesses #2.", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The strengths of this paper are summarized as follows:\n\n- The \"locally reverse Poincare inequality\" shown in this paper is intuitive and can be more general than previous studies.\n- The results are intuitive and improved the results in Chi et al. 2022 when the noise is sub-Gaussian.", "weaknesses": "The weaknesses of this paper are summarized as follows:\n\n**About contributions**\n\n1. The examples in this paper that satisfy the SID condition are still restricted to special additive models, which can be somehow not so practical. And it seems that extending the results to non-additive models is not easy. \n2. The discussions about optimality in [Line 279-285] are not so strict. Note that the lower bound of order $\\Omega(n^{-2 / (p + 2)})$ shown in Tan et al. 2022 is based on general additive models which may not satisfy the SID condition. In other words, when the SID condition satisfies, the lower bound may be better.\n\nTypos:\n- $\\kappa$ in [Line 242] seems to be not defined and it seems to be $\\tau$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your overall positive assessment of our work. \n\n\nReply to weakness 1/ question 1: \n\nThank you for this comment. Actually, it is possible to relax the additive model on $f^*$ such that it is ``approximately additive\". More precisely, we can assume that there is an additive function $g^*$ that approximates $f^*$, such that in each rectangle A, the L2 distance between $f^*$ and $g^*$ is bounded by a small constant of the variance of $f^*$ on $A$. \n\nOn the other hand, it seems hard to further relax this condition. Consider a two dimensional model $f^*(x_1,x_2)$ with features $X_1$ and $X_2$ independent. Suppose $E(f^*(X_1,X_2)) = 0$.\n    We can decompose $f^*$ into additive components and a remaining term:\n    \\begin{equation}\n    f^*(x_1,x_2) = f_1^*(x_1) + f_2^*(x_2) + h^*(x_1,x_2)\n    \\end{equation}\n\n where $f^*_1(x_1) := E(f^*(X_1,X_2) | X_1=x_1)$, $f^*_2(x_2) := E(f^*(X_1,X_2) | X_2=x_2)$ and $h^*(x_1,x_2) := f^*(x_1,x_2) - f_1^*(x_1) - f_2^*(x_2)$. Then it can be checked that \n    \\begin{equation}\n    E (h^*(X_1,X_2) | X_1) = E (h^*(X_1,X_2) | X_2) = 0\n    \\end{equation}\n\nIf the additive components $f^*_1 + f^*_2$ are small, say, in the extreme case $f^*_1 + f^*_2$ is zero, then $f^* = h^*$, and by the inequality above we know that the SID condition cannot be satisfied. Therefore, for the SID condition to be satisfied, it is necessary that the function $f^*$ has a significant amount of signal that is additive. \n\n But of course, this is for the SID condition to be satisfied. It is possible that CART can still work well without the SID condition, \n    which needs more exploration and is beyond the scope of this work.\n\n\n\nReply to weakness 2/ question 2:\n\nThank you for this comment. We will reword the discussion on optimality in line 279-285. \n    Indeed, if we consider the class of functions satisfying SID condition with a fixed parameter $\\lambda$, then the rate of Theorem 2.3 has an exponent with no explicit dependence dimension $p$. However, in multi-dimensional models, even for additive models satisfying the SID condition, the SID parameter $\\lambda$ seems to have a dependence on $p$. Therefore it is not proper to claim that it avoids the curse of dimensionality."}]

Author rebuttal:

Meta-review: This paper ends up with all bordeline+ reviews. I believe the paper could have been improved because (i) the additive structure has indeed been made previously but stays as a limitation of the approach (if the authors had managed to weaken it, it would have undeniably been a +); (ii) focusing only on CART is a formidable restriction in the context of the paper: we know what are the properties of proper losses (for class probability estimation), of which CART’s is just an instantiation. Being able to generalise to proper losses would carry the tremendous potential to balance boosting rates and conditions for consistency.

I hope that upon acceptance, the authors will dig in that last question for a longer version of the paper: the path forward on covering not just CART's loss could yield to very interesting conclusions (the authors may keep in mind that a loss function gives lots of indications on learning with it, not just on consistency, but also training rates, stability of optimization, etc.).
Decision: Accept (poster)