Why Split Geometry Can Defeat Consistency
A tree can make many splits without making its prediction local to the query point. If most splits remove only a thin slice of a cell, the remaining region may stay wide. A different failure occurs when the algorithm repeatedly ignores a coordinate on which the regression function depends. In either case, additional observations do not by themselves repair the geometry: a leaf prediction still averages responses across points with different regression means.
The counterexamples below isolate these mechanisms. They use a simple regression setting so that a failure of localization cannot be mistaken for irreducible response noise. Let \(X=(X_1,\ldots,X_d)\) be uniform on \([0,1]^d\), and take the regression function to be \(m(x)=E[Y\mid X=x]=x_1\). When useful, set \(Y=m(X)\) exactly. For a predictor \(\hat m\), its integrated squared prediction error for this noiseless model is \(R(\hat m)=E[(\hat m(X)-m(X))^2]\), where the expectation includes the test point and any tree randomization or training data used to construct the predictor.
Earlier material on shrinking leaf diameters and random-partition consistency explains why geometric localization matters. Here the aim is to see, by explicit risk calculations, what fails when the geometry does not shrink in a predictive direction.
A Lower Bound for a Wide Cell
The key calculation is elementary: no constant prediction can accurately represent \(m(x)=x_1\) across a long interval of \(x_1\). The bound applies even if the constant is selected using training data, since it holds for every possible value of that constant.
To verify the result, let the constant prediction be \(c\), and write \(L=b-a\) and \(u=(a+b)/2\). Completing the square gives \(\int_a^b (x-c)^2\,dx=\int_a^b (x-u)^2\,dx+L(c-u)^2\). The cross-term vanishes because \(\int_a^b(x-u)\,dx=0\). The first integral is \(L^3/12\), so the total is at least \(L^3/12\), with equality at \(c=u\). This is a bound on the integrated error, not a conditional average over the interval. \(\square\)
Worked Example: One Extremely Unbalanced Split
Let \(X\) be uniform on \([0,1]\), let \(Y=X\), and fit a tree with one deterministic split at \(t=0.01\). Whatever the two leaf predictions are, the prediction on the large leaf \([0.01,1]\) is a single constant \(c\).
The test-point risk contributed by that leaf is \(\int_{0.01}^{1}(x-c)^2\,dx\). The wide-cell result shows that this is at least \((1-0.01)^3/12=0.99^3/12=0.970299/12=0.08085825\).
The other leaf contributes a nonnegative amount, so total risk is at least \(0.08085825\), for every choice of the two predictions. This remains true if the leaf values are estimated from an arbitrarily large training sample. The split has created two leaves, but its small leaf has removed only one percent of the feature range; the large leaf still covers almost the whole range. For comparison, the constant best prediction on the unsplit interval has risk \(1/12\), approximately \(0.08333\). The split improves the geometric lower bound only slightly, not enough to make risk vanish.
The example also clarifies why a split-count condition alone is not a localization condition. If a query repeatedly follows the larger child of unbalanced splits, the interval remaining in its cell can stay wide. What matters is the cumulative reduction of width along the query's path, not the number of times a split was made.
Feature Starvation Leaves Predictive Variation Unresolved
A cell can be narrow in some coordinates and still be wide in a coordinate that matters. For \(m(x)=x_1\), splits on \(X_2,\ldots,X_d\) may partition those coordinates finely, but they do not distinguish points with different \(X_1\) values. The following result formalizes the resulting risk floor.
Proof. The uniform coordinates are independent, so \(X_1\) is independent of \(X_{-1}=(X_2,\ldots,X_d)\), with \(E[X_1]=1/2\) and \(\operatorname{Var}(X_1)=1/12\). For any fixed value of \(X_{-1}\), put \(c=g(X_{-1})\). Then \(E[(c-X_1)^2\mid X_{-1}]=\operatorname{Var}(X_1)+(c-E[X_1])^2=1/12+(c-1/2)^2\geq 1/12\). Taking expectation over \(X_{-1}\) proves the claim. \(\square\)
The argument does not require a tree: it applies to any predictor that is independent of the predictive coordinate. For a tree, that condition holds if its partition and prediction rule never use \(X_1\). It also holds for an average of trees if every tree is constrained to omit \(X_1\): averaging functions of \(X_{-1}\) still produces a function of \(X_{-1}\).
Worked Example: A Forest with a Starved Coordinate
Consider \(d=2\), \(X\) uniform on \([0,1]^2\), and \(Y=X_1\). Suppose a randomized forest first draws a feature mask shared by all its trees. With probability \(0.2\), the mask excludes coordinate \(X_1\); on that event, every tree may split on \(X_2\) as often as desired, but none can split on \(X_1\).
Conditional on exclusion, each tree's prediction is a function of \(X_2\) and its training data, not of the test value \(X_1\). The forest average has the same property. The theorem therefore gives conditional integrated risk at least \(1/12\). On the complementary event, risk is nonnegative. Averaging over the mask yields \(E[R]\geq 0.2(1/12)+0.8(0)=1/60\).
The lower bound does not assert that risk on the complementary event is zero; it uses only nonnegativity there. Nor does it disappear as the number of trees grows: all trees share the same feature mask, so adding trees cannot repair the event on which the predictive coordinate is unavailable. The example isolates a specific failure mode, rather than claiming that every random forest has such a shared mask.
Repeated Omission and Its Probability
Feature starvation can also be described by the probability of never selecting a coordinate along a path. Suppose a path has \(D\) split opportunities, and at each opportunity coordinate \(X_1\) is selected with probability \(q\), independently across opportunities. Then the probability of omitting \(X_1\) at every opportunity is \((1-q)^D\). If the entire forest uses a shared randomized selection rule that excludes \(X_1\) with probability \(\rho=(1-q)^D\), the preceding theorem gives expected forest risk at least \(\rho/12\). For example, if \(q=0.1\) and \(D=5\), then \(\rho=0.9^5=0.59049\), giving the lower bound \(0.59049/12=0.0492075\).
This calculation concerns the event of complete omission, not merely a small number of splits on \(X_1\). If the selection probability or depth changes with sample size, the event remains an obstruction whenever its probability is bounded away from zero and the prediction is independent of \(X_1\) on that event. If that probability tends to zero, this particular lower bound tends to zero; that fact alone does not prove consistency, because other failures such as persistent wide cells may remain.
For a single randomized tree, the same reasoning gives a lower bound on its risk averaged over tree randomization whenever the omission event has probability \(\rho\). An ensemble of independently randomized trees requires more care: averaging trees that do use \(X_1\) can yield a prediction that depends on \(X_1\), even if some members omit it. Thus a single-tree omission probability cannot automatically be multiplied by a risk bound to claim the same bound for an infinite forest. The shared-mask example avoids that issue because the event applies to the whole ensemble.
Empty Leaves and Bounded Defaults
Finite-sample leaf estimates require a convention for an empty leaf. A fixed default can lie outside the response range, so one must not infer that every prediction lies in that range. The relevant fact for a convergence argument is uniform boundedness when the response and the default are bounded.
Worked Example: An Empty Leaf with Default 2
Let \(X\) be uniform on \([0,1]\), let \(A=[0,1/2]\), and let \(Y\) be Bernoulli with success probability \(1/2\), independently of \(X\). For a query in \(A\), estimate its regression mean by the sample average of training responses whose covariates fall in \(A\); if there are no such observations, use the fixed default 2.
For a nonempty leaf, the estimate is an average of zeros and ones, and hence lies in \([0,1]\). For an empty leaf, it equals 2. Thus the estimator is uniformly bounded by 2 in absolute value, but it is not always between 0 and 1.
Let \(N\) be the number of training covariates in \(A\). Then \(N\sim\operatorname{Binomial}(n,1/2)\), so \(P(N=0)=2^{-n}\). The integrated squared error for queries in \(A\), measured against the regression mean \(1/2\), contributed by the empty-leaf event is exactly \(\frac12\cdot 2^{-n}\cdot(2-1/2)^2=\frac98\,2^{-n}\).
When \(N>0\), conditional on \(N\), the leaf average has mean \(1/2\) and variance \(1/(4N)\). Its expected squared error is therefore \(1/(4N)\). This contribution tends to zero: for any fixed integer \(K\), it is at most \(P(0<N<K)/4+1/(4K)\), and \(P(0<N<K)\to0\) by the binomial law. Taking the limit superior and then letting \(K\to\infty\) proves convergence to zero. The empty-leaf contribution also vanishes because \(2^{-n}\to0\). This example shows why the correct boundedness statement is that the estimator is uniformly bounded; on a nonempty leaf its average is in the response range, while the fixed default need not be.
Common Mistake and Practical Implications
Wrong reasoning: “The tree has increasing depth, so its leaves become small and its prediction risk must vanish.” Depth counts splits, not how much each split reduces the width of a cell or whether it splits a predictive coordinate. A deep tree can repeatedly shave off thin regions in one coordinate while leaving another coordinate untouched.
Correction: Track the geometry in the coordinates that control the regression function, and check how likely paths are to reduce those widths. The lower bounds here show that if a cell retains a long interval in \(X_1\), its constant prediction has unavoidable error for \(m(x)=x_1\); if a predictor omits \(X_1\) altogether, its risk is at least \(1/12\). In applications, inspect split frequencies and cell widths by coordinate rather than relying on depth or total split count alone.
Check Your Understanding
Work through these questions using the counterexamples and bounds above.
- For \(m(x)=x\) on \([0,1]\), what lower bound does a split at \(t=0.1\) give from the large leaf alone?
- Why does splitting only on \(X_2\) fail to reduce the \(1/12\) risk floor when \(m(x)=X_1\) and the features are independent and uniform?
- If the probability that a shared forest mask excludes \(X_1\) is \(0.05\), what risk lower bound follows from the feature-starvation result?
- Why is it incorrect to say that the empty-leaf estimator in the worked example always lies between 0 and 1?
- Why does a positive omission probability for one tree not, by itself, establish the same lower bound for an infinite ensemble of independently randomized trees?