When Persistent Leaves Prevent Consistency

Why Leaf Geometry and Occupancy Are Separate

A regression tree predicts at a query point by aggregating responses from observations in the same leaf. Two different features of that leaf matter. Its diameter describes how far apart covariate values in the leaf can be; its occupancy is the number of training observations it contains. A leaf can have many observations yet remain too broad to distinguish locations with different regression means. It can also shrink around a query while containing too few observations to average away response noise.

The examples below isolate these two defects. They show ways a defect can prevent consistency, not a claim that every estimator with a nonshrinking leaf or bounded occupancy must fail. For example, a broad leaf causes no approximation bias when the regression function is constant over it.

Definition: Let \(X\) take values in a subset of \(\mathbb{R}^d\), and let \(C_n(x)\) be the partition cell containing query point \(x\). Its diameter is \(\operatorname{diam}(C_n(x))=\sup\{\lVert u-v\rVert:u,v\in C_n(x)\}\). Given training covariates \(X_1,\ldots,X_n\), its occupancy is \(N_n(x)=\sum_{i=1}^n \mathbf{1}\{X_i\in C_n(x)\}\). The usual partition regression estimate is the average of the \(Y_i\)'s in that cell when \(N_n(x)>0\); an estimator must specify what it returns when the cell is empty.

Write \(m(x)=E[Y\mid X=x]\) for the regression function. Pointwise consistency at \(x\) means \(\hat m_n(x)\xrightarrow{p}m(x)\). Integrated squared-error consistency, for a specified covariate distribution, asks that \(E[\int(\hat m_n(x)-m(x))^2\,dP_X(x)]\) tend to zero. A counterexample to either property demonstrates a distinct form of failure.

Persistent Leaves Can Preserve Approximation Bias

If a leaf continues to cover locations where \(m\) takes different values, averaging all responses in that leaf estimates an average over locations, not the regression function at each individual location. More training data can make that average increasingly precise without making it a better local estimate.

Worked Example: One Leaf on the Entire Covariate Space

Let \(X_i\) be independent and uniform on \([0,1]\), and set \(Y_i=X_i\). Thus \(m(x)=x\), with no response noise. Use the partition with just one cell, \(C_n(x)=[0,1]\), for every query \(x\). Its diameter is 1 for every \(n\), and its occupancy is \(n\). The estimate is the sample mean \(\bar X_n\).

By the strong law of large numbers, \(\bar X_n\xrightarrow{a.s.}1/2\). Consequently, at any fixed \(x\ne 1/2\), \(\hat m_n(x)-m(x)=\bar X_n-x\xrightarrow{a.s.}1/2-x\), which is nonzero. The estimate is not pointwise consistent at those locations.

The integrated squared error can be calculated exactly:

\int_0^1(\bar X_n-x)^2\,dx = \left(\bar X_n-\frac12\right)^2+\frac1{12} \ \xrightarrow{a.s.}\ \frac1{12}.

The identity follows by writing \(\bar X_n-x=(\bar X_n-\tfrac12)+(\tfrac12-x)\); the cross-term integrates to zero, and \(\int_0^1(\tfrac12-x)^2dx=1/12\). The limiting error is positive despite the occupancy growing as fast as possible. The obstruction is that the leaf never localizes.

The same issue occurs with several persistent leaves. Their occupancy may grow in every region while each leaf still mixes covariate values whose regression means differ. The next calculation makes that separation explicit.

Worked Example: Two Fixed Leaves With Growing Occupancy

Again take \(X_i\) uniform on \([0,1]\) and \(Y_i=X_i\). Partition the covariate space into \([0,1/2)\) and \([1/2,1]\), and estimate by the sample response average in the query's cell. Each leaf has diameter \(1/2\). Its occupancy grows proportionally to \(n\) with probability tending to one.

Within the left leaf, the conditional mean of \(Y\) is \(E[X\mid X<1/2]=1/4\); within the right leaf it is \(E[X\mid X\ge 1/2]=3/4\). The law of large numbers for the cell counts and response sums therefore gives predictions tending almost surely to \(1/4\) and \(3/4\), respectively. At \(x=0.1\), the prediction tends to \(1/4\), so its error tends to \(1/4-0.1=0.15\), not zero.

The limiting integrated squared error is

\int_0^{1/2}(x-\tfrac14)^2\,dx + \int_{1/2}^1(x-\tfrac34)^2\,dx = \frac1{96}+\frac1{96} = \frac1{48}.

For the first integral, shifting by \(1/4\) gives \(\int_{-1/4}^{1/4}t^2dt=1/96\); the second is identical. The sample predictions and the limiting cell means lie in \([0,1]\), so squared errors are bounded by 1. Dominated convergence then also gives convergence of the expected integrated squared error to \(1/48\). Thus the defect remains even though both leaves receive increasing numbers of observations.

Proposition: For \(X\sim\operatorname{Unif}[0,1]\), \(Y=X\), and the one-leaf estimator above, the integrated squared error converges almost surely to \(1/12\). Hence increasing occupancy alone does not ensure regression consistency when a leaf continues to span a region where the regression function varies.

Proof. The estimate at every query is \(\bar X_n\). The strong law gives \(\bar X_n\xrightarrow{a.s.}1/2\). Expanding the integrated squared error yields \(\int_0^1(\bar X_n-x)^2dx=(\bar X_n-\tfrac12)^2+\int_0^1(\tfrac12-x)^2dx\), since the cross-term has integral zero. The remaining integral is \(1/12\), so the claimed limit follows. \(\square\)

Shrinking Leaves Can Still Retain Response Noise

Localization alone does not guarantee that a response average is stable. If the number of responses being averaged stays small, a noisy observation can continue to have a substantial effect on the prediction. The following example makes this failure quantitative at one fixed query point.

Worked Example: A Shrinking Leaf With Bounded Occupancy

Let \(X_i\) be independent and uniform on \([0,1]\), and let \(Y_i=\varepsilon_i\), where the \(\varepsilon_i\) are independent \(N(0,1)\) variables, independent of all covariates. The regression function is \(m(x)=0\). Fix \(x_0=1/2\). For \(n\ge2\), use the leaf \(C_n(x_0)=[1/2,1/2+1/n)\); the rest of \([0,1]\) can be partitioned into the other leaves. The diameter at \(x_0\) is \(1/n\), so it shrinks to zero.

The occupancy \(N_n(x_0)\) has the binomial distribution with \(n\) trials and success probability \(1/n\). In particular,

P\{N_n(x_0)=1\} = n\frac1n\left(1-\frac1n\right)^{n-1} = \left(1-\frac1n\right)^{n-1} \longrightarrow e^{-1}.

If the occupancy is one, the estimate is the single response in the leaf. Define the prediction to be zero for an empty leaf; this convention does not affect the event with occupancy one. Independence of the responses and covariates gives

P\{|\hat m_n(x_0)-m(x_0)|>1/2\} \ \ge\ P\{N_n(x_0)=1\}P\{|Z|>1/2\}, \qquad Z\sim N(0,1).

For a standard normal variable, \(P(|Z|>1/2)=2[1-\Phi(1/2)]\approx 0.617075\), where \(\Phi\) is the standard normal distribution function. Therefore,

\liminf_{n\to\infty}P\{|\hat m_n(x_0)-m(x_0)|>1/2\} \ge e^{-1}(0.617075)\approx 0.2270.

This positive lower bound rules out convergence in probability at \(x_0\). Shrinking the leaf has not made the estimate consistent because its occupancy does not grow: it remains of order one in distribution.

Proposition: In the shrinking-leaf example, the prediction at \(x_0=1/2\) is not consistent in probability. In particular, its probability of an absolute error greater than \(1/2\) has limit inferior at least \(e^{-1}2[1-\Phi(1/2)]\), approximately \(0.2270\).

Proof. On the event \(N_n(x_0)=1\), the prediction error is the one response in that leaf, which has distribution \(N(0,1)\) and is independent of the occupancy event. Thus the probability of an error exceeding \(1/2\) is at least the product of the probability of occupancy one and \(P(|Z|>1/2)\). The occupancy probability tends to \(e^{-1}\), while \(P(|Z|>1/2)=2[1-\Phi(1/2)]>0\). Taking the limit inferior proves the bound, which is incompatible with convergence in probability to zero. \(\square\)

What the Counterexamples Do—and Do Not—Show

The examples isolate two different contributions to regression error. A leaf that remains broad can produce approximation bias: observations far from the query contribute responses with different conditional means. A leaf with bounded occupancy can retain sampling noise: even if its covariates are close to the query, too few responses may be averaged for their noise to disappear. Shrinking diameter and growing occupancy address distinct obstacles.

Neither condition by itself is a universal theorem about every forest. A nonshrinking cell need not induce bias if \(m\) is constant on that cell. Likewise, bounded occupancy need not cause error when the responses are noiseless and the regression function is constant near the query. The examples establish that these defects can prevent consistency under ordinary, explicit regression models; they do not say that consistency logically forces each condition in every possible model.

A common mistake is to argue that a growing training sample automatically fixes either defect. In the one-leaf example, the average becomes highly accurate for the global mean \(1/2\), but that mean is not \(m(x)\) at most query points. In the shrinking-leaf example, the cell gets narrower, but its average does not become an average of an increasing number of independent responses. The relevant questions are what quantity the leaf average targets and how many observations support it.

Key takeaway: Localization controls how different the regression means within a leaf can be; occupancy controls whether response noise is averaged down. A persistent leaf can keep bias even with abundant data, and a shrinking leaf can keep noise when its occupancy fails to grow.

Check Your Understanding

For each question, distinguish the leaf's geometric behavior from the number of observations it contains.

In the one-leaf example, why does increasing occupancy fail to make the estimator pointwise consistent at \(x=0.2\)?
For the two-leaf example, verify that the limiting integrated squared error from either half of the covariate space is \(1/96\).
In the shrinking-leaf example, what is the limiting probability that the leaf contains exactly one training observation?
Why does the event of exactly one observation give a lower bound on the probability of an error larger than \(1/2\)?
Give a condition on the regression function under which a persistent leaf might not create approximation bias.

When Persistent Leaves Prevent Consistency

What You'll Learn