ADAPTIVE CONCENTRATION OF REGRESSION TREES,
WITH APPLICATION TO RANDOM FORESTS

arXiv:1503.06388v3 [math.ST] 30 Apr 2016

By Stefan Wager and Guenther Walther
Stanford University
We study the convergence of the predictive surface of regression
trees and forests. To support our analysis we introduce a notion of
adaptive concentration for regression trees. This approach breaks tree
training into a model selection phase in which we pick the tree splits,
followed by a model fitting phase where we find the best regression
model consistent with these splits. We then show that the fitted regression tree concentrates around the optimal predictor with the same
splits: as d and n get large,
p the discrepancy is with high probability
bounded on the order of log(d) log(n)/k uniformly over the whole
regression surface, where d is the dimension of the feature space, n is
the number of training examples, and k is the minimum leaf size for
each tree. We also provide rate-matching lower bounds for this adaptive concentration statement. From a practical perspective, our result
enables us to prove consistency results for adaptively grown forests
in high dimensions, and to carry out valid post-selection inference in
the sense of Berk et al. [2013] for subgroups defined by tree leaves.

1. Introduction. Trees [10] and random forests [8] are among the most
widely used machine learning predictors today, with applications in a broad
variety of fields such as chemistry [42], ecology [13, 35], genetics [16, 40], and
remote sensing [20, 34]. While allowing for flexible predictive surfaces and
complicated interactions, trees and especially random forests have proven
to be surprisingly resilient to over-fitting. Unlike competing non-parametric
techniques such as kernel methods or neural networks, random forests require
very little tuning; experience has shown that one can often obtain good
predictive models out-of-the-box with standard software like randomForest
for R [27]. However, from the perspective of existing results, we have no
particularly strong reasons to believe that forest predictions ought to be
well behaved in high dimensions: The best existing convergence results for
random forests either only provide fixed-dimensional asymptotic consistency
guarantees [10, 38], or assume a substantially simplified training procedure
where tree splits are chosen using a holdout dataset [5, 14].
Theoretical framework. The goal of this paper is to use adaptive concentration as a framework for describing the statistical properties of adaptively
grown trees, i.e., trees that have access to the full training data while placing
1

2

5

WAGER AND WALTHER

●

Fitted Tree
Optimal Tree

●

●

4

●

●

● ●

3

●

●
● ●●

● ●
●

2

Y

●
● ●●
● ●
●●
●●
●
●
●

1

●

0

●

●
●

●
●
●●
●

●
●
●●
●

●

●●

●

●

●
●

●

●

●

●

●
●● ●
●
●

●

●
●
●
●

●

●

●

●
●

●

●

●
●

●

●

●

●

●

● ●
●
●●

●

●

●

●●

●

●●

●

●

●

●

●

●
●

0.0

0.2

0.4

0.6

0.8

1.0

X

Fig 1: Adaptive concentration compares the prediction surface of the fitted
decision tree with that of the optimal decision tree with the same splits.
Here, the splits produced by recursive partitioning are denoted by dashed
vertical lines. The regression tree was fit using the R-package tree [44].

tree splits. The idea of adaptive concentration is to view training trees as
occurring in two stages: a model selection stage where we decide on which
splits to make, and a model fitting stage where we find the best regression
tree conditional on having made these splits. We then treat the splits made
by the tree as fixed, and show that the fitted regression tree is not much
worse than the optimal regression tree with the same splits. In other words,
we establish conditions under which sample averages over tree leaves L concentrate to population averages over L—even if the leaves L were chosen
after looking at the data. Figure 1 illustrates this goal for a one-dimensional
tree.
Our setting is closely related to the work of Berk et al. [4] on valid postselection inference, which provides convergence guarantees for estimated linear regression parameters that hold even if the regression model is selected
after looking at the data. In order to make the connection explicit, suppose
that we view trees as a form of adaptive regression, where each leaf L induces

ADAPTIVE CONCENTRATION OF TREES

3

an indicator feature for whether a given observation falls into the leaf. Our
result then directly induces a method for constructing confidence intervals
for the within-leaf mean responses that accounts for model selection in the
sense of Berk et al. [4] (see Section 2.3 for details).
Main results. We study an asymptotic regime where the dimension d of
the feature space, the number n of training examples and the minimum leaf
size k go to infinity together. Under mild regularity conditions, we show
that
p regression trees satisfy an adaptive concentration bound that scales as
log (n) log (d)/k. More specifically, with high probability and simultaneously for any leaf L induced by any regression tree, the discrepancy between
the sample-average response inside p
the leaf L and the population-average
response inside L differ by at most C log (n) log (d)/k, where C is a universal constant. In the context of Figure 1, this result translates into a uniform
bound on the distance between the “fitted” and “optimal” curves. We also
show that this rate of convergence is tight to within a constant factor.
Our result does not rely on major modifications to the random forest
training routine, and in particular holds for variants of the CART algorithm
[10] and the original proposal of Breiman [8]. The reason there is a dependence on n in the numerator of our bound is that, as the sample size grows,
the trees comprising the random forest can become deeper and so the model
family becomes larger.
Finally, as an application of our adaptive concentration result, we establish consistency guarantee for adaptively grown random forests—i.e., forests
that do not use a holdout set for variable selection—that hold in a sparse,
high-dimensional setting. To our knowledge, no directly comparable results
are currently available in the literature (see Section 3 for details).
Outline. This paper is structured as follows. We first state and discuss our
main adaptive concentration bound in Section 2, and then apply this result
to provide consistency results for high-dimensional random forests in Section
3. Our theoretical work is carried out in Section 4, where we develop the
necessary tools to prove the results from the first sections. Section 5 derives
matching lower bounds for the adaptive concentration rate of regression
trees.
2. Adaptive Concentration. To give adaptive concentration bounds,
we first need to disambiguate the hierarchy of concepts used to build forest
predictors: a forest is an ensemble of trees, each of which relies on a partition
of the data generated by a splitting rule. We begin by providing formal
definitions of these quantities below; we state our main result in Section 2.2.
Throughout our analysis, we assume that we have a set of n independent

4

WAGER AND WALTHER

and identically distributed training examples (Xi , Yi ) satisfying Xi ∈ [0, 1]d
and Yi ∈ [−M, M ].
2.1. A Review of Recursive Partitioning. The first concept underlying
a regression tree is the splitting rule itself, which induces a partition Λ of
[0, 1]d into non-overlapping rectangles L1 , ..., Lm . We use the short-hand
L(x) to denote the unique element of Λ containing x. We are interested in
those partitions that can be obtained by recursive partitioning of the feature
space [10]. Starting from a parent node ν = [0, 1]d , recursive partitioning
operates by repeatedly selecting a currently unsplit node ν ⊆ Rd , a splitting
variable j ∈ {1, ..., d} and a threshold τ ∈ [0, 1], and then splitting ν into
two children ν− = ν ∩ {x : xj ≤ τ } and ν+ = ν ∩ {x : xj > τ }. The final
leaf nodes generated by this algorithm, denoted by L, form a partition Λ
of [0, 1]d . Given our training set {(Xi , Yi )}, we require the partition to be
valid in the sense of Definition 1.
Definition 1 (Valid partition). A partition Λ is {α, k}-valid if it can
by generated by a recursive partitioning scheme in which each child node
contains at least a fraction α of the data points in its parent node for some
0 < α < 0.5, and each terminal node contains at least k training examples for
some k ∈ N. Given a dataset X , we denote the set of {α, k}-valid partitions
by Vα, k (X ).
The constraint that each terminal node must have at least k observations
is implemented by default in, e.g., randomForest. Meanwhile, the requirement that each child node must incorporate at least a fraction α of the data
in its parent—and thus that the tree cannot be excessively imbalanced—is
more substantive. It is known that CART-like rules tend to split near the
edges of noise features [10, 23]; thus our α-constraint may make splits along
noise features less desirable. A similar assumption is also used by, e.g., [31].
A partition Λ can then be used to induce a tree predictor by averaging
the responses Yi over its leaves Lj . In our adaptive concentration analysis,
we consider two kinds of trees: valid trees (1) that are fit to the training
sample, and partition-optimal trees (2) that would arise if we could train a
tree supported on the partition Λ using the full population.
Definition 2 (Valid and partition-optimal trees).
duces a valid tree
(1)

TΛ : [0, 1]d → R, TΛ (x) =

1
|{Xi : Xi ∈ L(x)}|

A valid partition inX
{i:Xi ∈L(x)}

Yi .

5

ADAPTIVE CONCENTRATION OF TREES

We denote the set of all {α, k}-valid trees TΛ with Λ ∈ Vα, k (X ) by Tα, k (X ).
Given a partition Λ, we also define the partition-optimal tree as
(2)

TΛ∗ : [0, 1]d → R, TΛ∗ (x) = E [Y |X ∈ L(x)] ,

where (X, Y ) is a new random sample from our data-generating distribution.
Forests are, as their name suggests, ensembles of regression trees. Generating a regression forest involves growing multiple trees; then, the forest
prediction is the average of all the tree predictions. In general, the choice of
splitting splitting variables j is randomized to ensure that the different trees
comprising the forest are not too correlated with each other. As shown by
Breiman [8], the variance reduction of a forest in comparison with its constituent trees improves as the correlation between individual trees decreases.
For any B ∈ N, let

Definition 3 (Valid and partition-optimal forests).
TΛ(1) , ..., TΛ(B) ∈ Tα, k (X ). Then, the average
(3)

H{Λ}B
1

B
1 X
: [0, 1] → R, H{Λ}B (x) =
TΛ(b) (x)
1
B
d

b=1

is a valid forest; we denote the set of {α, k}-valid forests by Hα, k (X ). The
corresponding partition-optimal forest is defined as
(4)

∗
d
∗
H{Λ}
H{Λ}
B : [0, 1] → R,
B (x) =
1

1

B
1 X ∗
TΛ(b) (x).
B
b=1

∗
When there is no risk of ambiguity, we write H := H{Λ}B and H ∗ = H{Λ}
B.
1

1

There are many proposals for how to choose the splitting variables j and
the thresholds τ for trees. Our theoretical results, however, do not depend
on the specific splitting rules used, and only rely on the generic structure of
recursive partitioning; thus, we will not focus on specific splitting rules in
this paper. For a review of how trees and forests are implemented in practice,
we recommend Hastie et al. [21] (see Chapters 9.2 and 15).
Remark: Bootstrapping. One way in which our forests from Definition 3
differ from the original proposal of Breiman [8] is that we do not allow the
individual trees to be evaluated on bootstrap samples.1 It seems plausible,
1

Technically, we could use a bootstrap sample to pick the partition Λ, but would then
need to use the whole training set to turn Λ into a tree TΛ .

6

WAGER AND WALTHER

however, that all our results should still hold even if we allow for bootstrapping, since the bootstrap is thought to have a regularizing effect on the
forest and should thus reduce its ability to overfit the training data [7, 11].
Studying the effect of the bootstrap on our adaptive concentration bounds
and perhaps showing how it can improve adaptive concentration guarantees
presents a promising avenue for further work.
2.2. An Adaptive Concentration Bound. We are now ready to state our
main result, given some assumptions on the problem setting. Our first condition is a bound on the dependence of the individual coordinates (Xi )j for
j = 1, ..., d.
Assumption 1 (Weakly dependent features). We have n independent
and identically distributed training examples, whose features X ∈ [0, 1]d
are distributed according to a density f (·) satisfying ζ −1 ≤ f (x) ≤ ζ for all
x ∈ [0, 1]d , and some constant ζ ≥ 1.
The above assumption is quite general. In contrast, consider the following
condition: We have features Xi ∈ Rd that admit a density satisfying
(5)

ζ −1

d
Y

fj (xj ) ≤ f (x) ≤ ζ

j=1

d
Y

fj (xj ) for all x ∈ Rd .

j=1

Although the above may at first glance appear weaker than Assumption 1,
it is actually slightly more restrictive. Because trees are invariant to monotone transformations of the features (Xi )j , we can without loss of generality
rescale the features such that Xi ∈ [0, 1]d with uniform marginals. Applying
this transformation to (5) would yield Assumption 1, along with a uniformity
constraint on the marginals of f (·).
Next, although we allow for the minimum leaf size k to be quite small,
we still need for it to grow with n. Note that since k ≤ n, the assumption
below implicitly requires that log(d)  n/ log(n).
Assumption 2 (Minimum leaf size).
with n at a rate bounded from below by
(6)

The minimum leaf-size k grows

log (n) max {log(d), log log(n)}
= 0.
n→∞
k
lim

The following theorem is our main result on the adaptive concentration
of decision trees. This result implies that, in practical data analysis, we can

ADAPTIVE CONCENTRATION OF TREES

7

treat the fitted prediction function TΛ as a good approximation to the optimal tree TΛ∗ supported on the partition Λ. This result
requires
 no continuity

assumptions on the conditional mean function E Y X = x .
Theorem 1. Suppose that we have n training examples (Xi , Yi ) ∈ [0, 1]d ×
[−M, M ] satisfying Assumption 1, and that we have a sequence of problems
with parameters (n, d, k) satisfying Assumption 2. Then, sample averages
over all possible valid partitions concentrate around their expectations with
high probability:

lim

n, d, k→∞

(7)

P

sup
x∈[0, 1]d , Λ∈Vα, k

|TΛ (x) − TΛ∗ (x)|


v
u log (n/k) (log(dk) + 3 log log(n)) 1
u


√  = 1.
≤ 9M t
k
log (1 − α)−1

In a moderately high-dimensional regime with lim inf d/n > 0, the above
bound simplifies to


v
u log (n) log (d) 1
u


√ 
(8) P 
sup
|TΛ (x) − TΛ∗ (x)| ≤ 9M t
 → 1.
−1
k
x∈[0, 1]d , Λ∈Vα, k
log (1 − α)
This result appears to be remarkably strong. As a baseline, suppose we
just selected a single tree T ∈ Tα, k (X ) non-adaptively, i.e., without looking
at the labels Yi . Then, a simple Hoeffding bound where we take n as a crude
upper for the total number of leaves shows that
"
#
r
2.1 log (n)
∗
(9)
P sup |T (x) − T (x)| ≤ M
→ 1.
k
x∈[0, 1]d
√
Moreover, assuming that k is not too large, say k ≤ n, and that the tree
is fully grown to depth k, the bound (9) is essentially tight.
Comparing (8) with (9), we see that a uniform concentration
bound valid
p
for all possible trees in Tα, k (X ) is only a factor O( log(d)) weaker than
the best concentration bound we could hope for with a single tree. In other
words, the “cost” of adaptively searching over p
all valid trees in high dimensions is surprisingly low, and only scales with log(d).
In Section 5, we provide a rate-matching lower bound to Theorem 1 that
holds for d = nr for some r ≥ 1. Thus, it is not possible to substantially
improve on the above result without restricting the class of considered trees.

8

WAGER AND WALTHER

Finally, because Theorem 1 holds simultaneously for all trees T ∈ T , we
note that (7) and (8) also induce adaptive concentration bounds for random
forests. The following result is conceptually related to the work of Biau et al.
[6], who established conditions under which ensembles inherit consistency
properties of their base classifiers, despite potentially allowing for greater
representational power.
Corollary 2. Under the conditions of Theorem 1, and assuming that
lim inf d/n > 0, we find that


v
u log (n) log (d) 1
u


√ 
(10)
P  sup |H (x) − H ∗ (x)| ≤ 9M t
 → 1.
−1
k
x∈[0, 1]d
log (1 − α)
simultaneously for all valid forests H constructed as in Definition 3.
Several authors have studied the theoretical properties of trees and forests
in order to explain their performance [1, 5, 6, 9, 14, 19, 28, 31, 33, 37, 38, 39,
45]. In particular, Scornet et al. [38] use low-dimensional asymptotics prove
that Breiman’s original forests are consistent in terms of their predictive risk,
while Biau [5] and Denil et al. [14] discuss the properties of some random
forests where trees are grown using only a holdout set—i.e., without looking
at the training data used for predictions. To our knowledge, however, our
above result is the first convergence guarantee for the predictive surface of
tree-based regression that holds in an asymptotic regime where n and d go
to infinity together, and does not require the use of a holdout set.
2.3. Adaptive Concentration as Post-Selection Inference. We can also
interpret Theorem 1 directly as a result about statistical inference for adaptive regression. To motivate this view, suppose that we build a tree-based
model to do subgroup analysis on data from a clinical trial with the intent of,
e.g., prioritizing treatment to patients in leaves with the largest estimated
treatment effect [2, 41]. In this case, it is crucial to have valid post-selection
confidence intervals for the treatment effect within each leaf that account
for the adaptive model search done by the tree.2
At a high level, the problem of post-selection inference for trees is a special
case of post-selection inference for adaptive least-squares regression. In the
classical adaptive regression setup, we start with a design X ∈ Rn×d and
2
Given an unconfoundedness assumption [36], results about regression trees and forests
can directly be adapted to the problem of heterogeneous treatment effect estimation; see
Section 4 of Wager and Athey [45] for an example.

ADAPTIVE CONCENTRATION OF TREES

9

a response Y ∈ Rn ; the statistician then selects a model M ⊆ {1, ..., d}
and provides estimates of the form ŷ = Aβ̂A , where A := XM ∈ Rn×|M|
is the matrix comprised of the columns of X contained in the set M [e.g.,
4, 18, 26].
In contrast, as in Definition 2, a valid tree first generates a partition Λ =
{Lj }m
j=1 , and then averages the responses Yi inside each leaf Lj . Formally,
this procedure is equivalent to creating a design matrix
A ∈ {0, 1}n×m , where Aij = 1 ({Xi ∈ Lj }) ,
and then running linear regression on A and the response vector Y . In other
words, regression trees are a form of adaptive regression where instead of
subsetting a list of available variables, we build a design matrix by considering indicator functions over leaves.
For any such adaptively-constructed design A, we can define the optimal
regression vector

−1


∗
βA
= A> A
A> µi where µi = E Yi Ai ;
∗ , where
it is then natural to ask about the discrepancy between β̂A − βA
>
−1
>
β̂A = (A A) A Y is the ordinary least squares estimate in the adaptive
regression model. In the case of subgroup analysis with trees, β̂A corresponds
∗ encodes the
to the measured mean responses in each tree leaf, whereas βA
population averages over the same leaves.
∗ for sparse linear reThe problem of bounding the gap between β̂A − βA
gression, i.e., where A = XM for some feature subset M, has been studied
in detail by Berk et al. [4]. The authors show that it is possible to honestly
account for arbitrary model selection by inflating standard confidence intervals for linear regression by a PoSI constant K that depends
√ on X. For
orthogonal designs, the optimal PoSI constant
scales
as
K
∼
2 log d; how√
ever, there also exist designs for which K ≥ d/2. Moreover, computing the
PoSI constant is in general difficult; the method used by Berk et al. [4] only
works for d ≤ 20.
In contrast, our Theorem
p1 shows that, for adaptively grown regression
∗
trees, kβ̂A − βA k∞ = Op ( log(n) log(d)/k); in otherpwords, there exists
a universal PoSI constant for trees on the order of log(n) log(d). This
is somewhat worse than the PoSI correction for linear regression with an
orthogonal design, but is exponentially better than general-case performance
for sparse linear regression.

10

WAGER AND WALTHER

2.4. Adaptive Concentration vs. Generalization Bounds. There is a long
tradition of studying the convergence of regression trees using arguments in
the style of Vapnik and Chervonenkis [43]—including the work of Breiman
et al. [10] and, more recently, [3, 15, 29, 30, 32]. The goal of these papers
is to control the generalization error of regression trees, i.e., the difference
between the training error and the expected test error of the tree.
In our context, we can use [30] to obtain the following generalization
bound:
n
h
i
1X
sup
(Yi − T (Xi ))2 − E (Y − T (X))2
T ∈Tα, k n i=1
!
r
# {leaves} (log (d) + log (n))
= OP
(11)
n
!
r
log (d) + log (n)
= OP
.
k
Strikingly, the rate of convergence in (11) is better than the adaptive concentration rate obtained in Theorem 1. Now, given our matching lower bound
(see Theorem 15), we know that our rates are optimal in moderately high
dimensions; thus, good adaptive concentration must be fundamentally more
difficult than good generalization.
The reason for this discrepancy is that generalization bounds only seek to
control the global performance of regression trees, whereas adaptive concentration requires local control of the tree regression surface. To give a concrete
example, suppose that d = nr for some r > 0. Then, the bound (11) implies
that the empirical risk of a regression tree will be consistent for the test set
error of the same tree provided that k  log(n). Meanwhile, our adaptive
concentration analysis implies that there exist trees with bad leaves unless
k  log(n)2 ; however, these bad leaves will be rare enough as to not affect
the overall test set error of the tree.
Generalization bounds vs. adaptive concentration bounds can both be relevant in different practical applications. If all we care about is the test error
of a tree, then the bound (11) is more useful than Theorem 1. Conversely,
if we want to use a regression tree to identify outlying sub-populations,
then we need guarantees as in Theorem 1, whereas the rate (11) might be
misleading.
3. Consistency of High-Dimensional Random Forests. As one
practical application of Theorem 1, we obtain consistency guarantees for
random forests in a high-dimensional setting. We work in a regime where

ADAPTIVE CONCENTRATION OF TREES

11



n, d → ∞, but the conditional mean function E Y X = x only depends
on a small number of covariates:
Assumption 3 (Sparse signal). There is a signal set Q ∈ {1, ..., d} of
size |Q| ≤ q such that the set of random variables {(Xi )j : j 6∈ Q} is jointly
independent of Yi and the set {(Xi )j : j ∈ Q}.
We study a simple CART-like regression forest that can consistently estimate sparse signals in high dimensions, described in Procedure 1. Effectively,
the algorithm is an extreme form of the procedure of Breiman [8], where each
splitting variable is chosen uniformly at random from {1, ..., d}. However,
in a break from classical regression trees, our algorithm uses Theorem 1 to
test the significance of a candidate split: if we have never split on a variable
j yet, then our tree will only split along j if it leads to a large enough improvement in mean-squared error. Once the tree has split along j once, then
this feature is “unlocked” and can be subsequently used without testing.3
At a high level, our construction relies on a guarantee from Theorem 1 that
no noise feature j will ever appear significant enough to get unlocked at any
stage of the forest-generation process.
To guarantee consistency of guess-and-check forests, we still need two
additional conditions to hold. Assumption 4 is a weaker version of an assumption made by Scornet et al. [38] to ensure that trees can eventually
accumulate evidence enabling them to split along signal coordinates. The
continuity assumption is standard for consistency proofs [e.g., 5, 6, 31, 38].
Assumption 4 (Monotone signal). There is a minimum effect size β > 0
and a set of sign variables σj ∈ {±1} such that, for all j ∈ Q and all
x ∈ [0, 1]d ,
 

1
σj E Yi (Xi )−j = x−j , (Xi )j >
2


1
− E Yi (Xi )−j = x−j , (Xi )j ≤
≥ β,
2
where x(−j) ∈ [0, 1]d−1 denotes the vector containing all but the j-th coordinate of x.


Assumption 5 (Continuity). The function E Y X = x is Lipschitzcontinuous in x.
3
Running a hypothesis test before accepting a split for a regression tree has also been
considered by Zeileis et al. [47]; however, the paper does not provide any formal consistency
guarantees.

12

WAGER AND WALTHER

Procedure 1.

Guess-and-Check Forest

Input: n training examples of the form (Xi , Yi ), a minimum leaf size k, and a balance
parameter α.
Guess-and-check trees recursively apply the following splitting procedure until no
more splits are possible, i.e., until all terminal nodes contain less than 2k training
examples or there were no possible splits satisfying (12) to begin with.
1. Select a currently unsplit node ν containing at least 2k training examples.
2. Pick a candidate splitting variable j ∈ {1, ..., d} uniformly at random.
3. Pick the minimum squared error splitting point θ̂. More specifically,
θ̂ = argmax ` (θ) :=

4 N − (θ) N + (θ)
∆2 (θ)
(N − (θ) + N + (θ))2

such that θ = (Xi )j for some Xi ∈ ν
α |{i : Xi ∈ ν}| , k ≤ N − (θ) , N + (θ)
X
X


where ∆ (θ) =
Yi N + −
Yi N − ,
{i:Xi ∈ν(x), (Xi )j >θ}
{i:Xi ∈ν(x), (Xi )j ≤θ}
N − (θ) = |{i : Xi ∈ ν, (Xi )j ≤ θ}| ,
N + (θ) = |{i : Xi ∈ ν, (Xi )j > θ}| .
4. If either there has already been a successful split along variable j for some
other node or
!2
s
 
log (n) log (d)

(12)
` θ̂ ≥ 2 × 9M
,
k log (1 − α)−1
the split succeeds and we cut the node ν at θ̂ along the j-th variable; if not,
we do not split the node ν this time.
A guess-and-check forest is the average of B independently generated guess-and-check
trees.

Given this setup, our first result is a uniform consistency result for guessand-check forests in high dimensions; recall that, as in Theorem 1, we assume
that the minimum leaf size k grows faster than log(n) log(d). We take the
signal dimension q to be fixed.
Theorem 3. Under the conditions of Theorem
 1 with lim inf d/n > 0,
suppose that ŷ(x) are estimates for E Y X = x obtained using a guessand-check forest (Procedure 1). Suppose, moreover, that Assumptions 3, 4,
and 5 hold. Then,


lim
sup ŷ (x) − E Y X = x = 0.
n d, k→∞ x∈[0, 1]d

ADAPTIVE CONCENTRATION OF TREES

13

To our knowledge, this is the first pointwise consistency result for adaptively grown random forests in high dimensions. Scornet et al. [38] prove
that random forests are consistent; however, their proof only works in a
regime where d is fixed while n → ∞. Meanwhile, in high dimensions, Biau
[5] establishes a rate of convergence for random forests that only depends
on the signal dimension q and not on d. However, his proof assumes a form
of data splitting, where we first effectively do variable selection on a holdout
sample, and then grow non-adaptive trees on the training sample without
looking at the responses Y .
We also consider the predictive error of our guess-and-check forests. To
do so, we focus on a special variant of guess-and-check trees with “α = 0.5”,
meaning that θ̂ in step 3 of Procedure 1 is always set to the median of the
(Xi )j with Xi ∈ ν. The idea of building trees by splitting along leaf medians
goes back to at least Devroye et al. [15], and the behavior of median forests
in low dimensions has been studied in detail by Duroux and Scornet [17].
The following result hinges on showing that our median guess-and-check
forest, with examples in [0, 1]d , converges as fast as a standard median
forest with examples in [0, 1]q . We can thus recover the rates of convergence
of Duroux and Scornet [17] that only depend on q. In order to apply the
result of Duroux and Scornet [17], we need to require the Xi to be uniformly
distributed over [0, 1]d , i.e., ζ = 1 in Assumption 1.
Theorem 4. Set α = 0.5, and define ξ = 1/(1 − 3/(4q)). Suppose that
the conditions of Theorem 1 with lim inf d/n > 0 and Assumptions 3, 4 and
5 hold, and moreover that Xi is uniformly distributed over [0, 1]d . Then, the
excess error rate of the guess-and-check tree (Procedure 1) satisfies:


h
log(ξ)
log(ξ)
2 i

− log(2 ξ)
(13)
E ŷ (X) − E Y X
=O n
, given k  n log(2 ξ) .
The result below is a direct analogue to the result of Biau [5], except that
our trees are adaptive, i.e., grown as usual by considering the Y sample;
whereas his result required a holdout sample for variable selection. As noted
by Biau, as soon as q < 0.54 d, the rate (13) is better than the standard rate
for non-parametric estimation of Lipschitz functions, i.e., n−2/(d+2) .
Finally, we note that Assumption 4 was only used as a crude tool to
ensure that the guess-and-check forest succeeds at splitting on all the signal
variables; given Assumptions 3 and 5, our proof shows that guess-and-check
forests will be consistent as long as the trees in fact split on the signal
variables. Empirically, greedily trained regression trees have been found to
be powerful under substantially weaker conditions than Assumption 4, so we
expect a relaxation to be possible; however, we leave this to further work.

14

WAGER AND WALTHER

3.1. Proof Sketch. In this section, we briefly outline the main steps in
proving our forest consistency results using Theorem 1. We begin by showing
that, as n, d → ∞, guess-and-check trees (Procedure 1) never split on noise
variables. We emphasize that the following result holds simultaneously for
all random realizations of the guess-and-check forest.
Lemma 5. Under the conditions of Theorem 1 with lim inf d/n > 0,
suppose moreover that Assumption 3 holds. Let πbad be the probability that
any guess-and-check tree ever splits on a noise variable j 6∈ Q. Then, πbad =
√
O(1/ n).
In order to achieve consistency, we also need to make enough splits along
the signal variables. The following lemma guarantees that, given Assumption
4, a guess-and-check tree will almost always split on a signal variable when
it gets a chance to do so.
Lemma 6. Suppose Assumptions 3 and 4 hold. For any variable j for
any j ∈ Q, let πj be the probability that the first time any guess-and-check
√
tree tries to split along j, the split succeeds. Then πj = 1 − O(1/ n).
Given these two lemmas, we see that a d-dimensional guess-and-check
tree with a q-dimensional signal effectively behaves like a q-dimensional tree.
Then, to prove Theorems 3 and 4, it suffices to use existing results about
the consistency of random forests in low dimensions; we in particular build
on the work of Duroux and Scornet [17] and Meinshausen [31].
4. Theoretical Development. We now develop the technical machinery required to prove Theorem 1. The bulk of our work goes into bounding
large deviations of the process
X


1
(14)
Yi − E Y X ∈ L ,
|{i : Xi ∈ L}|
{i:Xi ∈L}

where L ranges over the set Lα, k of all possible leaves of a valid partition
Λ ∈ Vα, k . Our argument proceeds as follows.
First, in Section 4.2, we construct a parsimonious set of rectangles R such
that any leaf L ∈ Lα, k can be well-approximated by a rectangle R ∈ R under
Lebesgue measure λ(·). More specifically, for any large enough L ∈ Lα, k ,
we require
that there exist√ R− , R+ ∈ R such that R− ⊆ L ⊆ R+ , and
√
k
−1/
e
λ(R+ ) ≤ λ(L) ≤ e1/ k λ(R− ).
Then, in Section 4.3, we establish concentration bounds for the process
(14) that only depend on the cardinality of the approximating set R. The

ADAPTIVE CONCENTRATION OF TREES

15

main step here is in showing that the rectangles R− and R+ constructed
above are also good approximations to L under the empirical measure; for
example, if R− is an inner approximation to L, then R− cannot contain too
many fewer training examples than L. The technical results from Sections
4.2 and 4.3 directly yield Theorem 1, as explained in Section 4.4. Proofs are
given in the appendix.
4.1. Notation. Throughout our analysis, we assume that we have n labeled independent and identically distributed training examples (Xi , Yi ) ∈
[0, 1]d × R. We denote rectangles R ∈ [0, 1]d by
(15)

R=

d h
O

i
rj− , rj+ , where 0 ≤ rj− < rj+ ≤ 1 for all j = 1, ..., d,

j=1

writing the Lebesgue measure of R as λ (R)
(16)

λ (R) =

d 
Y


rj+ − rj− .

j=1

Recall that, by Assumption 1, the features Xi have a distribution f (·) satisfying ζ −1 ≤ f (x) ≤ ζ for all x ∈ [0, 1]d . Given this setting, we write the
expected fraction of training examples falling inside R as µ(R), and the
number of training examples Xi inside R as #R:
Z
(17)
µ (R) =
f (x) dx, #R = |{i : Xi ∈ R}| .
R

Notice that, marginally, #R ∼ Binomial (n, µ (R)). For any rectangle R, we
define its support as
n
o
(18)
S(R) = j ∈ 1, ..., d : rj− 6= 0 or rj+ 6= 1 ;
these are the features used in defining R. Finally, we write Lα, k for the set of
all possible leaves associated with a valid partition Λ ∈ Vα, k . This notation
is summarized in Table 1.
4.2. A Set of Approximating Rectangles. Our first result effectively bounds
the complexity of the space of rectangles over the unit cube by showing how
all such rectangles can be well-approximated using an economical set of rectangles R. We detail a constructive characterization of R in Section 4.2.1;
this construction is a generalization of the one used by Walther [46] to study
the asymptotics of the multidimensional scan statistic [24].

16

WAGER AND WALTHER
Table 1
Summary of notation.
n
d
k
α
Vα, k
Lα, k
Tα, k
Hα, k
ζ
λ(R)
µ(R)
#R
S(R)

Number of training examples
Dimension of feature space: X ∈ [0, 1]d
Minimum leaf size
Bound on the allowable imbalance in recursive partitioning
Set of {α, k}-valid partitions; see Definition 1
Set of all leaves generated by {α, k}-valid partitions
Set of {α, k}-valid trees; see Definition 2
Set of {α, k}-valid forests; see Definition 3
Bound on the dependence structure of X; see Assumption 1
Lebesgue measure of a rectangle R; see (16)
Expected fraction of training examples in a rectangle R; see (17)
Number of training examples inside a rectangle R; see (17)
Support of a rectangle R; see (18)

Theorem 7. Let S ∈ {1, ..., d} be a set of size |S| = s, and let w, ε ∈
(0, 1). Then, there exists a set of rectangles RS, w, ε such that the following
properties hold. Any rectangle R with support S(R) ⊆ S and of volume
λ (R) ≥ w can be well approximated by elements in RS, w, ε from both above
and below in terms of Lebesgue measure. Specifically, there exist rectangles
R− , R+ ∈ RS, w, ε such that
(19)

R− ⊆ R ⊆ R+ , and e−ε λ (R+ ) ≤ λ (R) ≤ eε λ (R− ) .

Moreover, the set RS, w, ε has cardinality bounded by


 s
1 8s2
1
(20)
|RS, w, ε | ≤
1 + log2
· (1 + O (ε)) .
2
w ε
w
In order to approximate all possible s-sparse rectangles, we use the set
Rs, w, ε = ∪|S|=s RS, w, ε

(21)
of size
(22)

   2
 s
1
d 1 8s
1 + log2
· (1 + O (ε)) .
|Rs, w, ε | ≤
2
s w ε
w

Now, given our tree construction as encoded in Definition 1, each child node
must be smaller than its parent by at least a factor 1 − α; thus, for any
L ∈ L, #L ≤ (1 − α)|S(L)| n, and so
(23)

|S(L)| ≤

log (n/#L)
log (n/k)
≤
.
log (1/ (1 − α))
log (1/ (1 − α))

ADAPTIVE CONCENTRATION OF TREES

This implies that, by setting

(24)
s=

17


log (n/k)
+ 1,
log (1/ (1 − α))

we can use Rs, w, ε to approximate all possible tree leaves L ∈ Lα, k to
within error ε under Lebesgue measure λ(·), provided the leaves have volume λ(L) ≥ w. We end this section with a useful bound on the size of the
approximating set Rs, w, ε .
Corollary 8.
(25)

Suppose that we set







1 k
1
log
(n/k)

  + 1,
w=
, ε = √ , and s = 
2ζ n
k
log (1 − α)−1

where 0 < α < 0.5 and ζ ≥ 1 are fixed constants. Then,
log (|Rs, w, ε |) ≤
(26)

log (n/k) (log (dk) + 3 log log(n))


−1
log (1 − α)

+ O (log (max {n, d})) .
4.2.1. Constructing Approximating Rectangles. Without loss of generality, we can take S = {1, ..., s}; thus, our job is to ε-approximate all rectangles R ∈ [0, 1]s of volume at least w. When s = 1, it is easy to verify
that we can construct an approximating set containing on the order of w−2
elements that ε-approximate all possible intervals of length greater than
w: we can build such a set by, e.g., considering all rectangles of the form
[a · wε/2, b · wε/2] where a and b are integers.
A naive extrapolation of this idea may suggest that, as s grows, the number of required rectangles scales as w−2s : this is what we would get by varying
all the parameters rj− and rj+ freely. However, as shown by the construction
below, this guess is much too
Q pessimistic. The reason for this is that the
volume constraint λ(R) = sj=1 (rj+ − rj− ) ≥ w becomes more and more
stringent as the dimension s grows, because every dimension along which
rj− 6≈ 0 or rj+ 6≈ 1 geometrically cuts the size of λ(R). For example, we can
immediately verify that if λ(R) ≥ w, then rj+ − rj− ≤ 0.5 can can hold for
at most log2 (w−1 ) coordinates.
The construction below exploits the intuition that at most a few coordinates can be active on a small scale. Generalizing
N ideas from [46], we define
R as the set of all rectangles of the form R = sj=1 [rj− , rj+ ], with
n
wε
wε o
rj− = aj 2τj −1
(27)
and rj+ = min 1, rj− + w2τj + bj 2τj −1
,
s
s

18

WAGER AND WALTHER

such that
(28)
(29)

 
j
s k
2s
,
aj ∈ 0, 1, .., 21−τj
, bj ∈ 0, 1, ..,
wε
ε
 
s
X
1
−1
τj ∈ 0, 1, ..., blog2 w c, and
− s.
τj ≥ (s − 1) log2
w
j=1

In this construction, the j-th interval [rj− , rj+ ] is on the scale w 2τj . The
observation that only a few coordinates
Psj can be active on a small scale is
encoded in the lower bound (29) on j=1 τj . The lemma below confirms
that this this approximating set is valid.
Lemma 9. Given any rectangle R with support S(R) ⊆ S and volume
λ (R) ≥ w, we can select rectangles R− and R+ satisfying (19) from the
approximating set R defined above.
To complete our characterization of the approximating set, it suffices to
bound the cardinality of R. This computation is carried out in the Appendix,
in the proof of Theorem 7.
4.3. Uniform Concentration over Rectangles. In the previous section, we
showed how to ε-approximate all possible tree leaves under the Lebesgue
measure on [0, 1]d . However, to understand the behavior of decision trees,
we do not want to approximate tree leaves in terms of Lebesgue measure,
but rather in terms of the empirical measure induced by the training features {Xi }ni=1 , which, given our assumptions, are uniformly distributed over
[0, 1]d .
The following result lets us get around this issue by showing that the
empirical measure induced by the training examples is concentrated enough
that, with high probability, the set Rs, w, ε is also a good approximating set
in terms of the empirical measure induced by the training data.
Theorem 10. Suppose that Assumption 1 holds, and that we have a
sequence of problems indexed by n with values of d and k satisfying Assumption 2. Let Rs, w, ε be as defined in (21) with s as in (24), and choose ε and
w such that
(30)

1
1 k
ε = √ , and w =
,
2ζ n
k

where ζ ≥ 1 is the constant from Assumption 1. Then, there exists an n0 ∈ N
such that, for every n ≥ n0 , the following statement holds with probability

ADAPTIVE CONCENTRATION OF TREES

19

at least 1 − n−1/2 : for every possible leaf L ∈ Lα, k , we can select a rectangle
R ∈ Rs, w, ε such that R ⊆ L, λ (L) ≤ eε λ (R), and
q
(31) #L − #R ≤ 3 ζ 2 ε#L + 2 3 log (|Rs, w, ε |) #L + O (log (|Rs, w, ε |)) .
We can then turn this result into a concentration bound on our empirical
process of interest (14), provided we have a tail bound on the responses Yi . In
the following result, we obtain such a tail bound by imposing a uniform subGaussianity requirement on the conditional distribution Y X ∼ G (·; X).
We define a conditional distribution G (·; X) to be uniformly sub-Gaussian if
there is a constant M > 0 for which the following holds. For any X-marginal
distribution X ∼ FX (·) supported
on [0, 1]d and t > 0, the resulting Y R
marginal distribution FY (·) = G (·; X) dFX satisfies:
h
i
1 2
2
(32)
EY ∼FY et(Y −m) ≤ e 2 t M , where m = EY ∼FY [Y ] .
Note that if Y is bounded by M , i.e., |Y | ≤ M almost surely, then (32) can
immediately be verified using standard results.
Corollary 11. Suppose that the conditions of Theorem 10 hold, that
the parameters ε and w are chosen as in (30), and that the conditional
distribution of Y given X is uniformly sub-Gaussian in the sense of (32).
Then, there exists an n0 ∈ N such that, for all n ≥ n0 , the following holds
√
with probability at least 1 − 2/ n:
(
X
1
sup
Yi − E [Y |X ∈ L]
#L
L∈L
{i:Xi ∈L}
(33)
)
r
 log (|R

√
s, w, ε |)
≤ 0.
− 2M + 4 3 sup {|Yi | : Xi ∈ L}
k
4.3.1. Proof Sketch for Theorem 10. Here, we present a series of technical
results that lead up to Theorem 10. We begin with the following technical
lemma, which follows from the Chernoff-Hoeffding concentration bound. In
practice, we will always use Lemma 12 with R set to our finite approximating
set Rs, w, ε .
Lemma 12.

Fix a sequence δ(n) > 0, and define the event
) s
(


|R|
|#R − n µ(R)|
p
(34) A : sup
: R ∈ R, µ (R) ≥ µmin ≤ 3 log
δ
n µ (R)

20

WAGER AND WALTHER

for any set of rectangles R and threshold µmin . Then, for any sequence of
problems indexed by n with
(35)

log (|R|)
= 0, and
n→∞ n µmin
lim

δ −1
= 0,
n→∞ |R|
lim

there is a threshold n0 such that, for all n ≥ n0 , we have P [A] ≥ 1 − δ. Note
that, above, A, R, µmin , and δ are all implicitly changing with n.
For now, the relation (34) is only valid for rectangles R contained in R,
which we will take to be our finite approximating set Rs, w, ε . In general,
however, the leaves L ∈ Lα, k we want to study will not be in Rs, w, ε . The
following result lets us move beyond this issue by providing a bound that is
valid for all rectangles R, not just those in Rs, w, ε .
Lemma 13. Suppose that the event A defined in Lemma 12 has occurred
with R = Rs, w, ε and µmin = ζw, where ζ is the constant from Assumption
1. Then, all rectangles R with µ (R) ≥ ζw satisfy:
s


1 2
|Rs, w, ε |
ζ2ε
ζ
ε
#R ≤ e nµ (R) + e 2
3nµ (R) log
.
δ
Finally, in order for the above result to be useful for understanding the
leaves of decision trees, we need to show that all possible leaves L will satisfy
the condition µ (L) ≥ ζ w; the result below gives us such a guarantee. With
these results in hand, proving Theorem 10 reduces to algebra.
Corollary 14. Let A be the event from Lemma 12 with R = Rs, w, ε
√
and δ = 1/ n, and define the parameters s, w and ε as in the statement of
Theorem 10. Then, there exists an n0 ∈ N such that, for n ≥ n0 ,
(36)

inf

L∈Lα, k

{µ (L)} ≥ ζw on the event A.

4.4. Proof of Theorem 1. We have now gathered all the ingredients required to prove Theorem 1, which follows from combining Corollary 8 with
Corollary 11. In fact, the first bound (7) follows directly from these two
results by noting that sup |Yi | Xi ∈ L ≤ M (since Yi is bounded by as√
sumption) and that 2 + 4 3 < 9.
Now, if moreover lim inf d/n > 0, then we can verify that log(n) log(d) −
log(n/k) log(dk) ≥ 0 for large enough n, and so we can use Corollary 8 to
bound
log (n) log (d)
(37) log (Rs, n, ε ) ≤
+O (max {log (n) log (log (n)) , log(d)}) .
log (1 − α)−1

ADAPTIVE CONCENTRATION OF TREES

21

Thanks to our assumption that lim inf d/n > 0, the remained term is negligible and (8) holds.
5. Lower Bounds. In this final section, we complement our main adaptive concentration bound, and show that the convergence rate given in (8)
cannot be improved. Lin and Jeon [28] have also studied lower bounds for
forest convergence; however, they only consider non-adaptive forests and so
their lower bounds are substantially weaker. We show the following:
Theorem 15. For any r > 0, set d := d(n) = bnr c, and let α ≤ 0.2.
Then, there exists a distribution over (X, Y ) and a sequence k(n) satisfying
the conditions Theorem 1 for which


r
M log (n) log (d) 
sup
|TΛ (x) − TΛ∗ (x)| ≥
(38) lim P
= 1.
n→∞
5
k
x∈[0, 1]d , Λ∈Vα, k
Whenever, lim inf d/n > 0 (i.e., r ≥ 1), the rate (38) has the same dependence on n, d, and k as the upper bound (8), thus implying that our
adaptive concentration bound from Theorem 1 is rate optimal.
To establish Theorem 15, we take the Yi to be i.i.d. and independent of
X , with P [Y1 = M ] = P [Y1 = −M ] = 1/2. We will construct N = N (n)
nodes L1 , . . . , LN ∈ Vα, k (X ) and then consider for j = 1, . . . , N :
X
X
1
1
(39)
Tj :=
Yi , and Tej :=
Yei ,
#Lj
#Lj
{i:Xi ∈Lj }

{i:Xi ∈Lj }

where Tej is an approximation to Tt built using auxiliary random variables
Yei generated as
(40)

iid
Yei = Yi |Zi | where Zi ∼ N (0, 1) .

Notice in particular that the Yei are jointly distributed as independent Gaussian random variables with variance M 2 .
The idea of the proof is to construct a large set of candidate leaf nodes
whose pairwise intersections are small enough that the multivariate normal
distribution of the standardized Tej has correlations that are bounded away
from unity; note that the leaves Lj may be generated by different trees, and
are thus allowed to overlap. A normal approximation lemma [25] then allows
us to stochastically lower-bound the distribution of maxj Tej in terms of the
distribution of a correlated multivariate normal that can be constructed in
a simple way from an i.i.d. normal sequence. Specifically, we establish the
following lower bound of the tail of the Tej .

22

WAGER AND WALTHER

Lemma 16. For any r > 0, set d := d(n) = bnr c, and let α ≤ 0.2. Then,
there exists a sequence k = k(n) satisfying Assumption 2 and a set of N
{α, k}-valid candidate leaf nodes Lj chosen independently of the Yi and Yei ,
for which
"
#
r r
2
log(N
)
(41)
lim P max Tej ≥ 1.999 M
= 1, and
n→∞
j=1,...,N
5
k
(42)

log(N ) =

log (n) log (d)
(1 + o(1)) .
log(5)

In the second step, we establish a coupling between Ti and the Tei that is
tight enough to guarantee that the approximation error maxj {Tej − Tj } is
smaller than maxj Tej . To get this coupling, we use the following bound on
the moment-generating function of Yi − Yei .
Lemma 17. Let P [Y = 1] = P [Y = −1] = 1/2 and Z ∼ N (0, 1) independent of Y . Then
(
r ! )
2 2
(43)
E [exp {t (Y − Y |Z|)}] ≤ exp
(1 −
t
π
for t in a neighborhood of zero.
This lemma implies the bound on maxj {Tej − Tj } given below. The lower
bound in Theorem 15 then follows from
p Lemma 16√ and Corollary 18, together with the observation that 1.999 2/5 − 1 ≥ log 5/5.
Corollary 18. Suppose that the statistics Tj and Tej are constructed
as in (39 - 40), with leaves Lj chosen independently of the Yi and Yei . Then,
"
#
r
log (N )
e
(44)
lim P
max Tj − Tj ≤ M
= 0.
n→∞
j=1, ..., N
k
Acknowledgment. The authors are grateful for helpful feedback from
two anonymous referees.
References.
[1] Sylvain Arlot and Robin Genuer. Analysis of purely random forests bias. arXiv
preprint arXiv:1407.3939, 2014.
[2] Susan Athey and Guido Imbens. Machine learning methods for estimating heterogeneous causal effects. arXiv preprint arXiv:1504.01132, 2015.

ADAPTIVE CONCENTRATION OF TREES

23

[3] Peter L Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities:
Risk bounds and structural results. The Journal of Machine Learning Research, 3:
463–482, 2003.
[4] Richard Berk, Lawrence Brown, Andreas Buja, Kai Zhang, and Linda Zhao. Valid
post-selection inference. The Annals of Statistics, 41(2):802–837, 2013.
[5] Gérard Biau. Analysis of a random forests model. The Journal of Machine Learning
Research, 13(1):1063–1095, 2012.
[6] Gérard Biau, Luc Devroye, and Gábor Lugosi. Consistency of random forests and
other averaging classifiers. The Journal of Machine Learning Research, 9:2015–2033,
2008.
[7] Leo Breiman. Bagging predictors. Machine Learning, 24(2):123–140, 1996.
[8] Leo Breiman. Random forests. Machine Learning, 45(1):5–32, 2001.
[9] Leo Breiman. Consistency for a simple model of random forests. Statistical Department, University of California at Berkeley. Technical Report, (670), 2004.
[10] Leo Breiman, Jerome Friedman, Charles J Stone, and Richard A Olshen. Classification and Regression Trees. CRC press, 1984.
[11] Peter Bühlmann and Bin Yu. Analyzing bagging. The Annals of Statistics, 30(4):
927–961, 2002.
[12] Herman Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based
on the sum of observations. The Annals of Mathematical Statistics, 23(4):493–507,
1952.
[13] D Richard Cutler, Thomas C Edwards Jr, Karen H Beard, Adele Cutler, Kyle T Hess,
Jacob Gibson, and Joshua J Lawler. Random forests for classification in ecology.
Ecology, 88(11):2783–2792, 2007.
[14] Misha Denil, David Matheson, and Nando de Freitas. Narrowing the gap: Random
forests in theory and in practice. In Proceedings of The 31st International Conference
on Machine Learning, pages 665–673, 2014.
[15] Luc Devroye, László Györfi, and Gábor Lugosi. A Probabilistic Theory of Pattern
Recognition. Springer-Verlag, New York, 1996.
[16] Ramón Dı́az-Uriarte and Sara Alvarez De Andres. Gene selection and classification
of microarray data using random forest. BMC bioinformatics, 7(1):3, 2006.
[17] Roxane Duroux and Erwan Scornet. Impact of subsampling and pruning on random
forests. arXiv preprint arXiv:1603.04261, 2016.
[18] William Fithian, Dennis Sun, and Jonathan Taylor. Optimal inference after model
selection. arXiv preprint arXiv:1410.2597, 2014.
[19] Louis Gordon and Richard A Olshen. Almost surely consistent nonparametric regression from recursive partitioning schemes. Journal of Multivariate Analysis, 15
(2):147–163, 1984.
[20] Jisoo Ham, Yangchi Chen, Melba M Crawford, and Joydeep Ghosh. Investigation of
the random forest framework for classification of hyperspectral data. IEEE Transactions on Geoscience and Remote Sensing, 43(3):492–501, 2005.
[21] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical
Learning. New York: Springer, 2nd edition, 2009.
[22] Wassily Hoeffding. Probability inequalities for sums of bounded random variables.
Journal of the American Statistical Association, 58(301):13–30, 1963.
[23] Hemant Ishwaran. The effect of splitting on random forests. Machine Learning, 99
(1):75–118, 2015.
[24] Martin Kulldorff. A spatial scan statistic. Communications in Statistics-Theory and
methods, 26(6):1481–1496, 1997.
[25] Malcolm R Leadbetter, Georg Lindgren, and Holger Rootzén. Extremes and Related

24

WAGER AND WALTHER

Properties of Random Sequences and Processes. Springer-Verlag New York, 1983.
[26] Jason D Lee, Dennis L Sun, Yuekai Sun, and Jonathan E Taylor. Exact post-selection
inference with the lasso. arXiv preprint arXiv:1311.6238, 2013.
[27] Andy Liaw and Matthew Wiener. Classification and regression by randomForest. R
News, 2(3):18–22, 2002. URL http://CRAN.R-project.org/doc/Rnews/.
[28] Yi Lin and Yongho Jeon. Random forests and adaptive nearest neighbors. Journal
of the American Statistical Association, 101(474):578–590, 2006.
[29] Gábor Lugosi and Andrew Nobel. Consistency of data-driven histogram methods for
density estimation and classification. The Annals of Statistics, 24(2):687–706, 1996.
[30] Yishay Mansour and David A McAllester. Generalization bounds for decision trees.
In Conference on Learning Theory, pages 69–74, 2000.
[31] Nicolai Meinshausen. Quantile regression forests. The Journal of Machine Learning
Research, 7:983–999, 2006.
[32] Andrew Nobel. Histogram regression estimation using data-dependent partitions.
The Annals of Statistics, 24(3):1084–1105, 1996.
[33] Richard A Olshen. Tree-structured regression and the differentiation of integrals.
The Annals of Statistics, pages 1–12, 2007.
[34] M Pal. Random forest classifier for remote sensing classification. International Journal of Remote Sensing, 26(1):217–222, 2005.
[35] Anantha M Prasad, Louis R Iverson, and Andy Liaw. Newer classification and regression tree techniques: Bagging and random forests for ecological prediction. Ecosystems, 9(2):181–199, 2006.
[36] Paul R Rosenbaum and Donald B Rubin. The central role of the propensity score in
observational studies for causal effects. Biometrika, 70(1):41–55, 1983.
[37] Erwan Scornet.
On the asymptotics of random forests.
arXiv preprint
arXiv:1409.2090, 2014.
[38] Erwan Scornet, Gérard Biau, and Jean-Philippe Vert. Consistency of random forests.
The Annals of Statistics, 43(4):1716–1741, 2015.
[39] Clayton Scott and Robert D Nowak. Minimax-optimal classification with dyadic
decision trees. IEEE Transactions on Information Theory, 52(4):1335–1353, 2006.
[40] Tao Shi, David Seligson, Arie S Belldegrun, Aarno Palotie, and Steve Horvath. Tumor
classification by tissue microarray profiling: random forest clustering applied to renal
cell carcinoma. Modern Pathology, 18(4):547–557, 2005.
[41] Xiaogang Su, Chih-Ling Tsai, Hansheng Wang, David M Nickerson, and Bogong
Li. Subgroup analysis via recursive partitioning. The Journal of Machine Learning
Research, 10:141–158, 2009.
[42] Vladimir Svetnik, Andy Liaw, Christopher Tong, J Christopher Culberson, Robert P
Sheridan, and Bradley P Feuston. Random forest: a classification and regression tool
for compound classification and QSAR modeling. Journal of Chemical Information
and Computer Sciences, 43(6):1947–1958, 2003.
[43] Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative
frequencies of events to their probabilities. Theory of Probability & Its Applications,
16(2):264–280, 1971.
[44] William N Venables and Brian D Ripley. Modern Applied Statistics with S. Springer,
New York, fourth edition, 2002.
[45] Stefan Wager and Susan Athey. Estimation and inference of heterogeneous treatment
effects using random forests. arXiv preprint arXiv:1510.04342, 2015.
[46] Guenther Walther. Optimal and fast detection of spatial clusters with scan statistics.
The Annals of Statistics, 38(2):1010–1033, 2010.
[47] Achim Zeileis, Torsten Hothorn, and Kurt Hornik. Model-based recursive partition-

ADAPTIVE CONCENTRATION OF TREES

25

ing. Journal of Computational and Graphical Statistics, 17(2):492–514, 2008.
Department of Statistics
Stanford University
Stanford, CA-94305
E-mail: swager@stanford.edu
E-mail: gwalther@stanford.edu

26

WAGER AND WALTHER

LIST OF APPENDICES
A The Approximating Set of Rectangles
A.1 Proof of Lemma 9 . . . . . . . .
A.2 Proof of Theorem 7 . . . . . . . .
A.3 Proof of Corollary 8 . . . . . . .
B Concentration over Rectangles . . . .
B.1 Proof of Lemma 12 . . . . . . . .
B.2 Proof of Lemma 13 . . . . . . . .
B.3 Proof of Corollary 14 . . . . . . .
B.4 Proof of Theorem 10 . . . . . . .
B.5 Proof of Corollary 11 . . . . . . .
C Random Forest Consistency . . . . . .
C.1 Proof of Lemma 5 . . . . . . . .
C.2 Proof of Lemma 6 . . . . . . . .
C.3 Proof of Theorem 3 . . . . . . . .
C.4 Proof of Theorem 4 . . . . . . . .
D Lower Bounds . . . . . . . . . . . . . .
D.1 Proof of Lemma 16 . . . . . . . .
D.2 Proof of Lemma 17 . . . . . . . .
D.3 Proof of Corollary 18 . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

26
26
27
28
28
28
30
30
30
32
33
33
34
34
35
35
35
38
38

Remark. In this appendix, we present our proofs in the order of logical
dependence instead of the order in which they appear in the main text. For
example, Theorem 7 depends on Lemma 9, so we prove the lemma first.
APPENDIX A: THE APPROXIMATING SET OF RECTANGLES
A.1. Proof of Lemma 9. We focus on showing how to construct R+ ;
the construction of R− is analogous. Recall that, given a rectangle
R=

s h
O

s h
i
i
O
rj− , rj+ , our goal is to select a rectangle R+ =
qj− , qj+

j=1

j=1

from R such that R ⊆ R+ and λ (R+ ) ≤ eε λ (R) . In order to guarantee this,
it is sufficient to check that, for all j,


qj− ≤ rj− , rj+ ≤ qj+ , and qj+ − qj− ≤ eε/s rj+ − rj− .
Now, for each j, define
$
τj = log2

rj+ − rj−
w

%
,

ADAPTIVE CONCENTRATION OF TREES

27

let qj− be the largest choice of the form (28) such that qj− ≤ rj− , and pick qj+
analogously. These choices define a rectangle R+ in R such that R ⊆ R+ .
By construction, we immediately see that
r + −r −
j
j
−1
w

!

2

Ps

Ps

j=1 τj

≥2

j=1

log2

≥ 2−s w−(s−1) .

Moreover, by definition of τj
2τj w ≤ rj+ − rj− ≤ 2τj +1 w,
thus, we can verify that
qj+ − rj+ , rj− − qj− ≤ 2τj −1
This implies that


1ε +
wε
≤
rj − rj− .
s
2s



ε
qj+ − qj− ≤ rj+ − rj− 1 +
,
s

and so |R+ | ≤ eε |R|.
A.2. Proof of Theorem 7. Given Lemma 9, in order to complete the
proof of Theorem 7 it suffices to bound the cardinality of the approximating
set defined in Section 4.2.1. To do so, we first observe that for fixed values
of {τj }, the number of possible choices for the {aj } and {bj } is bounded by
s 
Y

j

1−τj

1+ 2

j=1


=


4s2
wε2

s

4s2

s


 
s k
2s
1+
wε
ε
2−

Ps



j=1 τj

· (1 + O (ε))

s
Y
rj+ − rj−

−1

 · (1 + O (ε))
2s 
wε2
w
j=1
 2 s
1 8s
=
· (1 + O (ε)) ,
w ε2


Q
because sj=1 rj+ − rj− ≥ w. Now, we can loosely bound the number of
s
possible choices for {τj } by 1 + log2 w−1 , yielding the desired bound.
≤

28

WAGER AND WALTHER

A.3. Proof of Corollary 8. Given the parameter choices (25), we can
verify that
   2 
 s

d 1 8s
1
log |Rs, w, ε | ≤ log
1 + log2
· (1 + O (ε))
s w ε2
w
 

d
= log
+ 2s log ε−1 + 2s log(s)
s

+ s log log w−1 + O (log (n)) .
Meanwhile,
 
d
log (n/k) log (d)

 + O (log (d)) ,
log
≤ s log (d) =
s
log (1 − α)−1
 1 log (n/k) log (k)

 + O (log (n)) , and
s log ε−1 =
2 log (1 − α)−1
 log (n/k) log log(n)

 + O (log (n)) .
s log (s) , s log log w−1 =
log (1 − α)−1
Combining these results, we recover (26).
APPENDIX B: CONCENTRATION OVER RECTANGLES
B.1. Proof of Lemma 12. The proof of this result relies on a union
bound. Our goal is to show that, for any rectangle R with R ∈ R and
µ (R) ≥ µmin , we can bound the large deviations of #R as follows: There is
some n0 ∈ N such that, for all n ≥ n0 ,


#R
δ
(45)
P
− µ (R) ≥ ∆ ≤
, where
n
|R|
s
r


µ(R)
|R|
(46)
∆=
3 log
.
n
δ
Verifying (45) then immediately implies the desired bound on P [A]. We
proceed in two parts. First, we verify that (45) holds for very large rectangles
with µ(R) ≥ 1/2; second, we consider the smaller rectangles with 1/2 >
µ (R) ≥ µmin .
In the case of large rectangles, we know that #R/n is sub-Gaussian with

ADAPTIVE CONCENTRATION OF TREES

29

parameter σn2 = 1/(4n). Thus,




#R
− µ (R) ≥ ∆ ≤ 2 exp −2n ∆2
P
n





|R|
δ 3
≤ 2 exp −3 log
≤2
,
δ
|R|
and (45) is easily satisfied.
In order to analyze small rectangles, we need the tighter binomial concentration result of Chernoff [12] and Hoeffding [22], stated below for convenience.
Proposition (Chernoff-Hoeffding). Let #R be a binomial (n, µ) random variable. Then

µ+∆ 
1−µ−∆ !n


#R
1−µ
µ
P
(47)
≥µ+∆ ≤
,
n
µ+∆
1−µ−∆


µ−∆ 
1−µ+∆ !n

#R
1−µ
µ
(48)
P
≤µ−∆ ≤
.
n
µ−∆
1−µ+∆
Now by (35), we know that ∆/µ(R) → 0 uniformly over our set of rectangles of interest. Moreover, because we are working with small rectangles
R, we also have ∆/(1 − µ(R)) < ∆/µ(R) → 0. Finally, we can verify by
calculus that
3
x2
1
≤ e−x+ 2 +|x| for all |x| ≤ 0.5.
1+x
Thus, for large enough n, the Chernoff-Hoeffding bound implies that for all
our rectangles of interest,


 

#R
∆
∆2
∆3
P
≥ µ + ∆ ≤ exp n
− + 2 + 3 (µ + ∆)
n
µ
2µ
µ



2
3
∆
∆
∆
+
+
+
(1 − µ − ∆)
1 − µ 2(1 − µ)2 (1 − µ)3


∆2
≤ exp −n
(1 + o(1)) .
2µ(1 − µ)
We can also apply the same argument to (48), and get for large enough n:




#R
∆2
P
− µ ≥ +∆ ≤ 2 exp −n
(1 + o(1))
n
2µ(1 − µ)


∆2
δ
≤ exp −n
≤
,
3µ(1 − µ)
|R|
thus concluding the proof.

30

WAGER AND WALTHER

B.2. Proof of Lemma 13. Because µ (R) ≥ µmin , we can use Assumption 1 to verify that λ (R) ≥ ζ −1 µ (R) ≥ w. Thus, by Theorem 7, we know
that there exists a rectangles R+ ∈ Rs, w, ε such that
R ⊆ R+ , and e−ε λ (R+ ) ≤ λ (R) .
Moreover, again by Assumption 1 and because R ⊆ R+ , we can verify that
µ (R+ ) ≤ µ (R) + ζ (λ (R+ ) − λ (R))
≤ µ (R) + ζ (eε − 1) λ (R)
≤ µ (R) + ζ 2 (eε − 1) µ (R)
2

≤ eζ ε µ (R) .
Then, we see that on A,
s




|Rs, w, ε |
#R ≤ #R+ ≤ nµ (R+ ) + 3nµ (R+ ) log
δ
s


1 2
|Rs, w, ε |
ζ2ε
ζ
ε
3nµ (R) log
,
≤ e nµ (R) + e 2
δ
where the second inequality followed by Lemma 12.
B.3. Proof of Corollary 14. By Lemma 13, we see that on A
s


1 2
|Rs, w, ε |
ζ2ε
ζ
ε
2
sup {#R : µ (R) = ζw} ≤ e ζnw + e
3ζnw log
δ
s


1 2
|Rs, w, ε |
3k
3k
ζ2ε k
ζ ε
2
=e
+e
log
<
,
2
2
δ
4
for large enough n. In other words, for large enough n, all rectangles of size
ζw can have at most 3k/4 points in them. Thus, we conclude that, on A,
any rectangle with k points must have size greater than ζw.
B.4. Proof of Theorem 10. For this whole proof, we assume that the
event A defined in Lemma 12 has occurred, with R = Rs, w, ε , µmin = ζw/2,
√
and δ = 1/ n. Note that, thanks to Assumption 2, these choices satisfy the
conditions (35), and so Lemma 12 implies that the is an n0 ∈ N such that
√
the event A must occur with probability at least 1 − 1/ n for all n ≥ n0 .
Given the event A, we first note that Corollary 14 implies that µ (L) ≥ ζ w
for all L ∈ Lα, k ; by Assumption 1, this also implies that λ(L) ≥ w for all

31

ADAPTIVE CONCENTRATION OF TREES

L ∈ Lα, k . Thus, by Theorem 7, for each possible leaf L ∈ Lα, k we can select
a rectangle R ∈ Rs, w, ε such that R ⊆ L and
λ (L) ≤ eε λ (R) .
This establishes the first part of our desired result.
Next, we need to control the counts #L and #R on A. First, by Lemma
13, we immediately see that, on A,
s


1 2
|Rs, w, ε | p
2
ζ ε
ζ
ε
e nµ (L) + e 2
3 log
nµ (L) − #L ≥ 0,
δ
or equivalently that
e−ζ
nµ (L) ≥
4

s

2ε

−



3 log

|Rs, w, ε |
δ

s


+

3 log



|Rs, w, ε |
δ

!2


+ 4#L

,

and so, because ε → 0 and we are in a regime where log (|Rs, w, ε |/δ)  #L,
we find that
s


 

|Rs, w, ε |
|Rs, w, ε |
ζ2ε
e nµ (L) ≥ #L − 3 log
#L + O log
.
δ
δ
Meanwhile, by Assumption 1,

µ(R) ≥ µ(L) − ζ (λ(L) − λ(R)) ≥ µ (L) − ζ 1 − e−ε λ(L)

≥ 1 − ζ 2 1 − e−ε µ(L) ≥ µmin ,
where the last inequality is valid provided ε is small enough (i.e., n is large
enough). Thus, because R ∈ Rs, w, ε , we can use Lemma 12 to verify that,
on A,
s


|Rs, w, ε |
#R ≥ nµ (R) − 3 nµ (R) log
δ
s



|Rs, w, ε |
2
−ε
≥ 1−ζ 1−e
nµ(L) − 3nµ (R) log
δ
s


|Rs, w, ε |
2
≥ e−2 ζ ε nµ(L) − 3nµ (R) log
δ
s


 

|Rs, w, ε |
|Rs, w, ε |
−2 ζ 2 ε
+ O log
≥e
nµ(L) − 3#R log
δ
δ
s


 

|Rs, w, ε |
|Rs, w, ε |
−2 ζ 2 ε
≥e
nµ(L) − 3#L log
+ O log
,
δ
δ

32

WAGER AND WALTHER

where the third inequality relies on ε being small enough, and the fourth
inequality relies on a second application of Lemma 12. Chaining these inequalities, together, we find that, on A and provided that n is large enough,
s




|Rs, w, ε |
−3 ζ 2 ε
−3 ζ 2 ε
#R ≥ e
#L − 1 + e
3#L log
δ

 
|Rs, w, ε |
.
+ O log
δ
p
√
Finally, by Assumption 1, ε = 1/ k  1/ log(|R|/δ), and moreover we
know that δ −1  |Rs, w, ε |; thus, the expression simplifies to
s


|Rs, w, ε |
2
#L − #R ≤ 3 ζ ε#L + 2 3 log
#L + O (log (|Rs, w, ε |)) .
δ
B.5. Proof of Corollary 11. Let A be the “good” set used in the
√
proof of Theorem 10; recall that P [A] ≥ 1 − 1/ n for large enough n.
Now, for any leaf L generated by a valid tree, let R ∈ Rs, w, ε be the inner
approximation for L constructed in Theorem 10. By the triangle inequality,


 1

X
sup
Yi − E [Y |X ∈ L] : L ∈ L
 #L

{i:Xi ∈L}

(
≤ sup

1
#L
(

+ sup

X
{i:Xi ∈L}

1
#R

1
Yi −
#R

)
X

Yi : L ∈ L

{i:Xi ∈R}

)
X

Yi − E [Y |X ∈ R] : R ∈ Rs, w, ε , #R ≥ k

{i:Xi ∈R}

+ sup {|E [Y |X ∈ R] − E [Y |X ∈ L]| : L ∈ L}
We can now proceed to bound each term individually. Starting with the first
term, we note that because R ⊆ L
1
#L

X
{i:Xi ∈L}

Yi −

1
#R

X
{i:Xi ∈R}

Yi ≤ 2 sup {|Yi | : Xi ∈ L}

#L − #R
,
#L

and by Theorem 10, on event A,
r




log |Rs, w, ε |
3 log |Rs, w, ε |
#L − #R
2
sup
: L ∈ L ≤ 3ζ ε + 2
+O
.
#L
k
k

ADAPTIVE CONCENTRATION OF TREES

33

Meanwhile, in order to bound the last term, we note that our uniform sub
Gaussianity
condition
implies that, for any points x1 and x2 , |E Y X = x2 −


E Y X = x1 | ≤ 2M . To see this, apply (32) with F (X) = 21 δ ({X = x1 })+
1
2 δ ({X = x2 }). Thus, we find that
|E [Y |X ∈ R] − E [Y |X ∈ L]| ≤ 2M


µ (L) − µ (R)
≤ 2M ζ 2 1 − e−ε ,
µ (L)

where the last inequality used Assumption 1 and the fact that λ(R) ≥
e−ε λ(L).
Finally, thanks to our uniform sub-Gaussiantiy assumption (32), we see
that—conditionally on #R—then mean of the Yi over R is sub-Gaussian
with parameter σ 2 = M 2 /#R. Moreover, by the proof of Theorem 10, we
see that the is an n0 ∈ N such that #R ≥ k/2 on the A whenever n ≥ n0 .
Thus, conditionally on A and provided that n ≥ n0 , the following event B
√
holds with probability at least 1 − 1/ n:
s
(
)
√
X
2 log (2|R| n)
1
B : sup
Yi − E [Y |X ∈ R]
≤M
.
#R
k/2
{i:Xi ∈R}

To verify this fact, we apply a union bound over the set of rectangles R ∈
Rs, w, ε with #R ≥ k/2. Combining all these bounds yields (33).
APPENDIX C: RANDOM FOREST CONSISTENCY
C.1. Proof of Lemma 5. By expanding the square, 4 N − N + / (N − +
≤ 1, and so `(θ) ≤ ∆2 (θ). Now, by Assumption 3, for all j 6∈ Q,




∆∗ (θ) := E Yi Xi ∈ ν, (Xi )j > θ − E Yi Xi ∈ ν, (Xi )j ≤ θ = 0.

N + )2

Moreover, we constructed the tree such that the sets {i : Xi ∈ ν, (Xi )j ≤ θ}
and {i : Xi ∈ ν, (Xi )j > θ} both have at most k observations. Thus, by
Theorem 1 and Corollary 11,
v
u log (n) log (d)
u
∗

,
|∆ (θ) − ∆ (θ)| = |∆ (θ)| ≤ 2 × 9M t
k log (1 − α)−1
√
with probability at least 1 − O(1/ n), uniformly over all possible nodes ν
with at least 2k observations and all variables j 6∈ Q. We conclude that, with
√
probability tending to 1 − O(1/ n), (12) is never satisfied for any j 6∈ Q,
uniformly over all nodes of all trees that can be generated as guess-and-check
trees.

34

WAGER AND WALTHER

C.2. Proof of Lemma 6. Let ν be the current node considered by
the algorithm, let j ∈ Q, and suppose that the node ν has never yet been
cut along the direction j. To establish the desired result, it suffices to show
that the split will succeed with probability tending to 1, uniformly over all
j ∈ Q and all possible nodes ν with at least 2k observations that have not
yet been divided along j. Our goal is to show that, with high probability,
the split at θ = 1/2 satisfies (12). Since the actual splitting point θ̂ is chosen
by maximizing `(θ), the result then also holds for θ̂.
We first note that, by Assumption 4,
 




1
1
∗ 1
∆
− E Yi Xi ∈ ν, (Xi )j ≤
= E Yi Xi ∈ ν, (Xi )j >
≥ β.
2
2
2
Thus, by Theorem 1 and Corollary 11, and by Assumption 2 on the minimum
√
leaf-size k, we see that with probability at least 1 − O(1/ n)
 
2 1
∆
≥ β 2 + o(1)
2
uniformly over all possible nodes. Next, by Lemma 13 and a similar argu√
ment, we again find that with probability at least 1 − O(1/ n)
4N− (1/2) N+ (1/2)
= 1 + o(1),
(N− (1/2) + N+ (1/2))2
uniformly over all possible nodes. Thus, (12) is in fact satisfied at θ =
1/2 with high probability, and the split will succeed with high probability
(although the split may not actually occur at θ = 1/2, as there may be even
more significant potential splitting points).
C.3. Proof of Theorem 3. We start by defining the following event
E: “all trees in the forest never split on any variable j 6∈ Q, and always split
on any variable j ∈ Q when j is drawn in phase 2 of the guess-and-check
procedure.” On this event, our d-dimensional guess-and-check tree is equivalent to a q-dimensional guess-and-check tree supported on the coordinates
j ∈ Q.
From Corollary 2, we already know that
!
r
log(n) log(d)
∗
sup |H(x) − H (x)| = Op
,
k
x∈[0, 1]d
where H(x) is our guess-check-tree and H ∗ (x) is the corresponding partitionoptimal forest in the sense of definition 3. Moreover, from Lemma 5 and

ADAPTIVE CONCENTRATION OF TREES

35

Lemma 6, we know that P [E] → 1. Thus, to obtain uniform consistency, it
only remains to show that, conditionally on E,


sup H ∗ (x) − E Y X = x = op (1).
x∈[0, 1]d
∗
Now,
comprising
H ∗ . Because


 let T  be a single partition-optimal tree
E Y X = x is Lipschitz in x, and because T ∗ (x) = E Y X ∈ L(x) , we
see that


T ∗ (x) − E Y X = x ≤ CLIP diam (L(x)) ,

where CLIP is the Lipschitz constant, and the diameter diam((L(x)) of the
leaf L(x) is defined as the longest line segment contained inside L(x). This
implies that


H ∗ (x) − E Y X = x ≤ CLIP E∗ [diam (L(x))] ,
where E∗ is an expectation over all trees comprising the forest. Finally, by
Lemma 2 of Meinshausen [31], we see that on event E
sup E∗ [diam (L(x))] = op (1),
x∈[0, 1]d

thus concluding the proof. We note that, in his paper, Meinshausen [31]
only discusses convergence at a single x; however, his proof is based on a
Kolmogorov-Smirnov argument that in facts holds uniformly for all x.
C.4. Proof of Theorem 4. We again define the same event E as in
the proof of Theorem 3. This time, since the tree effectively always splits at
the middle of a randomly selected feature j ∈ Q, our tree on event E is in
fact equivalent to a non-adaptive median tree trained on the feature set Q,
where each splitting variable is selected independently at random. This is
exactly the class of forests studied by Duroux and Scornet [17], who showed
that (13) in fact holds for them.
Now, thanks to Lemma 5 and Lemma 6, the probability of the event
√
E failing decays to 0 at a rate 1/ n. Thus, because our responses Y are
bounded, the risk accrued from failures of E is bounded on the order of
√
O(1/ n), which is vanishingly small relative to the rate in (13). Thus, we
conclude that (13) in fact holds for guess-and-check trees with α = 1/2.
APPENDIX D: LOWER BOUNDS
D.1. Proof of Lemma 16. For any 0 < α < 0.5, we study α-random
partitions generated as follows. Given dn = bnr c as assumed in Lemma 16,

36

WAGER AND WALTHER

we set
   3


log (n)
−1
s = sn := max 0, log
(log α)
and k = kn := bnαsn c .
n
Then k ≥ log3 (n) for all n ≥ 100, so Assumption 2 is met. Now, for each
index set S ⊂ {1, . . . , d} with |S| = s, define the partition ΛS as follows: For
each j = 1, ..., n, in order, if j ∈ S, then recursively split each leaf along the
j-th feature in such a way that each child-node contains at least a fraction α
of the data points in its parent-node, with one child-node containing exactly
a fraction α up to rounding. Given this construction, each terminal node L
has at least #L ≥ αs n ≥ k, so ΛS is in fact an {α, k}-valid partition.
Furthermore, the above construction provides for one terminal node L
that satisfies
#L ≤ αs n +

s−1
X
i=0

αi ≤ (k + 1) +

1
≤ k + 3.
1−α

For each s-combination S of {1,
 . . . , d} construct ΛS as described above.
Then for each of the N := ds s-combinations the resulting partition has
one terminal node with the above properties. Denote these N terminal nodes
by L1 , . . . , LN ; so for i = 1, . . . , N , k ≤ #Li ≤ k + 3. Moreover, if i 6= j
then the splits in Li and Lj occur on axes that differ in at least one index.
Since X has independent marginals we get
(49)

E [#(Li ∩ Lj )] ≤ αE [#Li ] + 1 ≤ αk + 3.

Since the overlap between the Lj is not very large, we might hope that
the maximum of the Tej would be of comparable size to the maximum of
2
N independent Gaussian random variables with variance #L−1
j M . The
following
√ sub-result shows that this intuition is valid, at least to within a
factor 1 − α.
Proposition. Assume that dn = nr for some r > 0. Then, given the
nodes Lj and statistics Tej as constructed above, and for any η > 0,
(50)
s
"
#
p
log(n)
log(d)
1
 √
lim P max Tej ≥ (1 − η) M 2(1 − α)
= 1.
n→∞
j=1,...,N
log α−1
k
The claim from Lemma 16 follows directly from (50) by noting that,
following our construction, an α̃-random partition is always an {α, k}-valid

ADAPTIVE CONCENTRATION OF TREES

37

partition for any α̃ ≥ α. Thus, if we know that α ≤ 0.2, we can apply (50)
for 0.2-random partitions, thus yielding the desired bound.
e
We now proceed
p to proving the sub-result. Independence of X and Y
e
implies that the #Lj Tj are standard normal, and so, for j 6= m:
#
"
hp
i
p
#(L
∩
L
)
j
m
Cov
#Lj Tej , #Lm Tem = M E p
#Lj #Lm




#(Lj ∩ Lm )
3
≤M α+
≤ ME
k
k
by (49). Now, let Z1 , . . . , ZN +1 be i.i.d. N (0, M 2 ) and for j = 1, . . . , N set
ej :=
Z

√
√
3
1 − αn Zj + αn ZN +1 , with αn := α + .
kn

ej are marginally normal with variance M 2 , and Cov[Zej , Z
em ] = αn M 2
The Z
if j 6= m. Using Corollary 4.2.3 to the normal
approximation lemma of
p
Leadbetter et al. [25], and the fact that #Lj /k ≤ 1 + 2/k, we get for
every u > 0:




 
√
p
2
e
e
P max
k Tj ≤ u ≤ P max
#Lj Tj ≤ 1 +
u
j=1,...,N
j=1,...,N
k


 
2
e
≤ P max Zj ≤ 1 +
u
(51)
j=1,...,N
k
"
#
√
(1 + k2 )u − αn ZN +1
√
= P max Zj ≤
.
j=1,...,N
1 − αn
p
p
Setting u = un := (1 − η)M 2(1 − α) log(n) log(d)/log(α−1 ), our goal is
to show that the above probability converges to 0. First, observe that


2un √
η/2
P
− αn ZN +1 ≤
un → 1
kn
1−η
because, by assumption, dn = bnr c whereas kn ∼ log(n)3 . Thus, by (51), it
suffices to verify that


1 − η/2
un
√
(52)
P max Zj ≤
→ 0.
j=1,...,N
1−η
1 − αn
Then, noting that
 
d
log(n) log(d)
log(N ) = log
= s log(d) (1 + o(1)) =
(1 + o(1)) ,
s
log (α−1 )
we can use a standard Gaussian tail bound to check that (52) in fact holds.

38

WAGER AND WALTHER

D.2. Proof of Lemma 17. One readily checks that
h
n
1

1

oi
E exp t Y − Y |Z|
= exp t2 + t Φ(−t) + exp t2 − t Φ(t),
2
2
where Φ is the cdf of Z. Using the expansion
∞
1
1 X (−1)k t2k+1
Φ(t) = + √
,
2
2π k=0 k!2k (2k + 1)

we find that
et Φ(−t) + e−t Φ(t)
r
∞
X
2
(−1)k t2k+1
sinh(t)
= cosh(t) −
π
k!2k (2k + 1)
k=0
!
! ∞
r
∞
∞
X
X (−1)k t2k+1
t2k
2 X t2k+1
=
−
(2k)!
π
(2k + 1)!
k!2k (2k + 1)
k=0
k=0
k=0
r !
1
2
1 4
=1 +
−
t2 +
t + O(t6 ).
2
π
4!
Lemma 17 follows since
1
<
4!

1
−
2

r !2

2
2 !.
π

D.3. Proof of Corollary 18. For simplicity, we take M = 1, and so
Yi ∈ ±1 and Var[Yei ] = 1. Q standard argument using Markov’s inequality
gives for any t, v > 0:
hp


i
P
#Lj Tej − Tj > v X
o
n p
≤ (E [exp {t (Y1 |Z1 | − Y1 )}])#Lj exp − #Lj tv






2
v
q 
≤ exp − 

 4 1− 2 

π

p

p
by Lemma 17, provided
that
t
:=
v/
2
#L
1
−
2/π is small enough.
j
√
Now, set v = vn := η log N for some fixed η > 0. First, recalling minj #Lj ≥

ADAPTIVE CONCENTRATION OF TREES

kn ≥ log3 n, we verify that in fact t → 0. Thus,



p 
p
e
P max
kn Tj − Tj > η log N
j=1,...,N
h hp


ii
≤ N max E P
#Lj Tej − Tj > vn X
j





2

η
 ,
≤ exp
log N 1 − 
p


4 1 − 2/π
which converges to zero provided that η 2 > 4 1 −

p

2/π > 0.8.

39

