Auditing Assumptions in Forest Consistency Theorems

What a Consistency Proof Must Actually Establish

A forest consistency claim is only as reliable as the chain of assumptions connecting its prediction to the regression function. A proof may correctly show that individual leaves contain many observations and still fail: the prediction weights might concentrate on one response, the selected observations might be far from the query point, or the splits might have used the very responses later treated as independent noise.

A useful audit begins by writing the prediction as a weighted average. For a fixed query point $x$, let $W_{ni}(x)$ be the forest weight on observation $i$, with $W_{ni}(x)\geq 0$ and $\sum_{i=1}^n W_{ni}(x)=1$. The estimate is $\hat m_n(x)=\sum_i W_{ni}(x)Y_i$. The weights can be random and depend on $n$. For an honest construction, they may depend on covariates, auxiliary randomization, and a separate structure sample, but the responses receiving estimation weight must not have been used to choose those weights.

The target is the regression function $m(x)=E[Y\mid X=x]$, at a point where a version of this conditional expectation is defined. The conditions below give a sufficient, not necessary, route to pointwise consistency: $\hat m_n(x)\xrightarrow{p}m(x)$. In particular, a finite conditional variance is a convenient way to control the noise; it is not a universal necessary condition for consistency.

Definition: The weights are spatially localized at $x$ if, for every $\epsilon>0$, $$ \sum_{i=1}^n W_{ni}(x)\mathbf{1}\{\|X_i-x\|>\epsilon\}\xrightarrow{p}0. $$ Their effective sample size is $1/\sum_i W_{ni}(x)^2$, when the denominator is positive. Small maximum weight, $\max_i W_{ni}(x)\xrightarrow{p}0$, is a direct sufficient condition for this effective sample size to diverge.

A Sufficient Consistency Result

Here is a precise benchmark against which to inspect a proposed forest argument. Let $(X_i,Y_i)$ be independent and identically distributed, with $Y_i=m(X_i)+\varepsilon_i$, where $E[\varepsilon_i\mid X_i]=0$. Fix $x$. Assume $m$ is bounded on the covariate support and continuous at $x$. Suppose the estimation responses are conditionally independent given the covariates and the information used to build the weights; conditional on that information, their residuals have mean zero and satisfy $E[\varepsilon_i^2\mid\cdot]\leq C$, for a constant $C$ not depending on $i$ or $n$. The weights are nonnegative, sum to one, and are measurable with respect to that conditioning information. Finally, suppose they are localized at $x$ and their maximum tends to zero in probability.

Theorem: Under the conditions just stated, $\hat m_n(x)\xrightarrow{p}m(x)$.

Proof. Decompose the estimation error into its weighted regression-function part and its weighted residual part:

\hat m_n(x)-m(x) = \sum_i W_{ni}(x)\{m(X_i)-m(x)\} + \sum_i W_{ni}(x)\varepsilon_i.

|B_n| \leq \frac{\eta}{2} +2M\sum_i W_{ni}(x)\mathbf{1}\{\|X_i-x\|>\delta\}.

By localization, the second term tends to zero in probability. Thus $P(|B_n|>\eta)\to0$, so $B_n\xrightarrow{p}0$.

For the residual sum $R_n=\sum_i W_{ni}(x)\varepsilon_i$, conditional mean-zero residuals and conditional independence eliminate the cross-covariance terms. Its conditional variance is bounded by

\operatorname{Var}(R_n\mid\cdot) = \sum_i W_{ni}(x)^2\operatorname{Var}(\varepsilon_i\mid\cdot) \leq C\sum_i W_{ni}(x)^2 \leq C\max_i W_{ni}(x).

The final inequality uses nonnegative weights summing to one. Since the maximum weight tends to zero in probability and lies between zero and one, its expectation tends to zero: for any $a>0$, $E[\max_i W_{ni}]\leq a+P(\max_i W_{ni}>a)$, and then take $n\to\infty$ followed by $a\downarrow0$. Conditional Chebyshev's inequality, averaged over the conditioning information, now gives $P(|R_n|>\eta)\leq C\eta^{-2}E[\sum_iW_{ni}^2]\to0$. Both parts tend to zero in probability, proving the result. $\square$

Worked Audits of the Conditions

Worked Example: A Large Leaf Can Still Have a Large Weight

Suppose a query point falls in a leaf containing $n$ estimation observations. Consider the weights $W_{n1}=1/2$ and $W_{ni}=1/\{2(n-1)\}$ for $i=2,\ldots,n$. They are nonnegative and sum to $1/2+(n-1)/[2(n-1)]=1$. The leaf occupancy is $n$, which diverges, but the largest weight remains $1/2$.

If the responses have independent mean-zero residuals with variance $\sigma^2$, then the residual variance of the prediction is

\sigma^2\sum_i W_{ni}^2 = \sigma^2\left\{\frac14+\frac{1}{4(n-1)}\right\} \longrightarrow \frac{\sigma^2}{4}.

So this occupancy fact alone does not make the noise vanish. In contrast, the effective sample size here is $1/\sum_i W_{ni}^2\to4$, not $n$. The relevant quantity for the variance argument is the distribution of weight across observations, not just the number present in the leaf.

Result: If exactly $k$ weights are nonzero, then $1/\sum_i W_i^2\leq k$. Indeed, Cauchy–Schwarz gives $1=(\sum_{i:W_i>0}W_i)^2\leq k\sum_iW_i^2$. Thus a diverging effective sample size requires a growing number of positively weighted observations; a growing count by itself does not guarantee it.

Worked Example: Occupancy Without Localization

Let $X_i$ be independent uniform variables on $[0,1]$, let $Y_i=X_i$ without noise, and predict at $x=0.5$. Define weights to be equal among observations with $X_i\leq0.1$, and zero otherwise. Write $N_n=\sum_i\mathbf{1}\{X_i\leq0.1\}$. The law of large numbers gives $N_n/n\xrightarrow{p}0.1$, so $N_n\to\infty$ in probability and the largest nonzero weight, $1/N_n$, tends to zero.

Nevertheless, every positively weighted covariate is at distance at least $0.4$ from the query point. Localization fails: for $\epsilon=0.3$, the total weight outside the $\epsilon$-ball is exactly one whenever $N_n>0$. The prediction is the average of the $X_i$'s below $0.1$; the conditional mean of a uniform variable on that interval is $0.05$, and the law of large numbers for this selected sample gives $\hat m_n(0.5)\xrightarrow{p}0.05$, not $m(0.5)=0.5$. More explicitly, the numerator divided by $n$ tends to $E[X\mathbf{1}\{X\leq0.1\}]=0.005$, while $N_n/n\to0.1$, so their ratio tends to $0.05$. Low variance and ample occupancy cannot repair a persistent spatial bias.

Worked Example: What a Second-Moment Assumption Does—and Does Not—Say

A common sufficient assumption is $E[\varepsilon_i^2\mid X_i]\leq C$. This makes the conditional variance calculation in the theorem available. It should not be misread as a necessary condition for every consistency result. For example, let $X$ be constant, set $m(X)=0$, and take independent symmetric residuals $\varepsilon=S R$, where $P(S=1)=P(S=-1)=1/2$, $R\geq1$, and $P(R>t)=t^{-3/2}$ for $t\geq1$.

The tail integral gives $E[R]=\int_0^1 1\,dt+\int_1^\infty t^{-3/2}\,dt=1+2=3$. Symmetry therefore gives $E[\varepsilon]=0$ and $E[|\varepsilon|]=3$. But $E[R^2]=\int_0^\infty 2tP(R>t)\,dt$ diverges, since its part from $1$ to infinity is $\int_1^\infty 2t^{-1/2}\,dt=\infty$. The ordinary sample average with weights $1/n$ is consistent for zero by the weak law of large numbers for independent identically distributed variables with finite first absolute moment. Its variance, however, is not finite, so the theorem's variance proof does not apply. A valid audit distinguishes “this proof needs a second moment” from “consistency is impossible without one.”

Honesty and Dependence Between Splits

A variance argument must check which data were used to construct the weights. If a response helps select a split and is then treated as a conditionally mean-zero estimation residual with fixed weight, the conditioning step in the proof may be invalid. Honesty addresses this issue by separating information used for partition construction from responses used for estimation. Conditional on the covariates and structure information, estimation weights must not depend on the estimation responses whose noise is being bounded. The precise design can vary, but the needed conditional independence or an alternative valid dependence bound must be stated.

Independence of trees is a different question. Trees built on the same training data can be dependent, and this dependence does not by itself invalidate the pointwise weighted-average argument above. The theorem uses properties of the resulting forest weights; it does not multiply a single-tree variance by an independence assumption across trees. Conversely, calling trees independent does not establish localization, control the largest observation weight, or make response-adaptive weights independent of estimation noise. Dependence matters insofar as it affects those properties or a separate Monte Carlo error calculation.

Worked Example: An Invalid Conditional Variance Shortcut

Let $X_i$ be constant and $Y_i=\varepsilon_i$, with independent $N(0,1)$ responses. A procedure selects the observation with the largest response and assigns it weight one. Its prediction is $\max_iY_i$. If one incorrectly conditions on the selected index and treats that response as an ordinary mean-zero residual, one might claim conditional variance at most one and infer vanishing noise from a “large sample.”

That conditioning is wrong: the index was selected using the responses, so the selected residual does not have the original $N(0,1)$ distribution or mean zero. In fact, for any fixed real $A$, $P(\max_iY_i\leq A)=\Phi(A)^n\to0$, since $0<\Phi(A)<1$. Thus the prediction does not converge to the target zero; it diverges upward in probability. This example is not an honest regression forest. It illustrates why response independence must be verified, not assumed from the appearance of a weighted-average formula.

Audit the Order of Limits

Forest results often involve several indices: sample size $n$, subsample size $s_n$, and number of trees $B$. Every asymptotic claim must say which quantities vary together. A condition such as “leaf occupancy tends to infinity” must hold along the actual sequence of forests under study. Fixing a subsample size while sending $n$ to infinity does not establish that condition if the leaf contains at most the fixed number of subsample observations.

There is also a difference between first defining an infinite-forest predictor at each fixed $n$, and proving consistency as $n$ grows, versus proving consistency for a finite-forest sequence $B=B_n$. The first route concerns the iterated limit in which $B$ is sent to infinity at fixed $n$, followed by $n\to\infty$. It says nothing by itself about an arbitrary joint sequence $B_n$. A finite-forest conclusion needs an error bound that controls the Monte Carlo approximation along that joint sequence.

Worked Example: Iterated Limits Do Not Guarantee a Joint Limit

Consider the numerical error sequence $a_{n,B}=n/B$. For each fixed $n$, $\lim_{B\to\infty}a_{n,B}=0$, and hence $\lim_{n\to\infty}\lim_{B\to\infty}a_{n,B}=0$. But along $B_n=\lfloor\sqrt n\rfloor$, $a_{n,B_n}=n/\lfloor\sqrt n\rfloor\to\infty$. For this particular bound, requiring $B_n/n\to\infty$ would make $a_{n,B_n}\to0$.

This sequence is an illustration of limit logic, not a universal forest Monte Carlo rate. A proof must derive the relevant error bound for its forest and then choose $B_n$ to satisfy that bound. Likewise, an argument that first fixes $s$ and later lets $n$ grow cannot establish a condition requiring $s_n\to\infty$; the subsample sequence must be included in the asymptotic statement.

A Practical Checklist and Common Mistake

When auditing a claimed consistency theorem, check the logical role of every condition rather than counting how many assumptions appear. The proof should identify its target and mode of convergence, give the conditioning under which weights are independent of estimation residuals, and show separately why the weighted regression-function part and the weighted noise part vanish. It should then verify those claims along the stated sequence of sample sizes and forest constructions.

Response moments: Is the target mean defined, and does the noise bound used in the proof actually hold conditionally? A variance argument cannot silently use an infinite or unspecified second moment.
Leaf occupancy: Does occupancy imply small maximum weights or diverging effective sample size, or is that implication merely asserted?
Localization: Does the total weight outside every fixed neighborhood of $x$ tend to zero? A small leaf is not automatically a local leaf.
Split dependence: Were estimation responses used to select the weights? If so, what valid argument replaces conditional independence?
Limits: Are $n$, $s_n$, and $B_n$ varied in the order the result requires? Is pointwise convergence being confused with an integrated or uniform claim?

A common mistake is to say, “Each leaf contains more observations, so the noise averages out.” The correction is to show that the weights spread over those observations, for example by proving $\max_iW_{ni}(x)\to0$, and that the weighted responses are conditionally centered given the information used to form the weights. Then verify localization separately to control bias. These are distinct steps; none follows just from a growing leaf count.

Key takeaway: A convincing forest consistency proof accounts for response noise, weight concentration, spatial bias, response-dependent splitting, and the actual asymptotic sequence. Passing one of these checks does not substitute for passing the others.

Check Your Understanding

For each question, identify the specific step in a consistency argument that it tests.

Why does a leaf with $n$ observations not necessarily have a diverging effective sample size?
State the localization condition in terms of the total forest weight outside an $\epsilon$-neighborhood of $x$.
In the sufficient theorem, which assumption permits the conditional variance bound for the residual term?
Can dependence among trees alone invalidate the weighted-average proof? What properties of the resulting weights still need checking?
Why does consistency of an infinite-forest predictor, defined by taking $B\to\infty$ at each fixed $n$, not automatically establish consistency for an arbitrary sequence $B_n$?