Consistency Conditions for Honest Subsampled Forests

Why Forest Consistency Needs Several Conditions

A tree can average many responses in each leaf and still predict poorly if its leaves remain too wide: observations far from the query point may have different conditional means. Conversely, leaves can shrink while containing too few estimation observations for their response noise to average out. For an honest subsampled forest, consistency therefore requires both localization and occupancy, as well as a sampling scheme that makes those conditions meaningful.

We give a sufficient theorem for regression. It applies whether a tree partition is fixed or chosen adaptively from a separate structure sample. The theorem does not assert that every forest-growing algorithm satisfies its geometric and occupancy assumptions; those properties must be verified for the algorithm under study.

Setup and Definitions

Let $(X_i,Y_i)$, $i=1,\ldots,n$, be independent and identically distributed, with $X_i\in[0,1]^d$. Let $X_0$ be an independent test covariate with the same distribution as $X_i$. Suppose a version $m(x)=E[Y\mid X=x]$ is continuous on the whole cube, and, almost surely,

E[(Y-m(X))^2\mid X]\leq \sigma^2

for a finite constant $\sigma^2$. Continuity on the compact cube implies $\|m\|_\infty=\sup_{x\in[0,1]^d}|m(x)|<\infty$. No density for $X$, or positive probability for every open subset of the cube, is required.

Definition: An honest subsampled tree draws a subsample of size $s_n$ without replacement from the $n$ observations, and divides it into a structure sample and an estimation sample of size $q_n$. Its partition may depend on the structure sample and independent randomization, but not on the estimation observations. For a query $x$, the tree predicts by averaging the estimation responses whose covariates lie in the same partition cell as $x$. If that cell contains no estimation covariate, define the prediction to be $0$.

Write $C_n(x)$ for the cell containing $x$, $K_n(x)$ for the number of estimation covariates in that cell, and $D_n(x)=\operatorname{diam}(C_n(x))$. These quantities are random because the subsample, partition, and query point may all be random. A forest prediction $F_n(x)$ here means the ideal forest: conditional on the observed data, it averages the tree prediction over the tree-sampling and randomization mechanism.

A Sufficient Consistency Theorem

Theorem: Suppose $s_n\leq n$, $s_n\to\infty$, and $s_n/n\to0$. Let $q_n$ be the number of estimation observations per tree, with $q_n\to\infty$ and $q_n\leq s_n$. Suppose the trees are honest as defined above. For a randomly selected tree and an independent query $X_0$, assume $$ D_n(X_0)\xrightarrow{p}0 \qquad\text{and}\qquad K_n(X_0)\xrightarrow{p}\infty. $$ Under the regression assumptions above, the ideal forest is mean-squared consistent: $$ E[(F_n(X_0)-m(X_0))^2]\longrightarrow 0. $$

The subsample conditions are explicit sufficient choices for this theorem; they are not claimed to be necessary. The proof uses the size and honesty of the estimation sample through its occupancy and noise, while localization controls the conditional-mean approximation.

Proof. First consider one randomly selected tree, and abbreviate its prediction by $T_n(X_0)$. Define the modulus of continuity $$ \omega_m(\delta)=\sup\{|m(x)-m(z)|:x,z\in[0,1]^d,\ \|x-z\|\leq\delta\}. $$ Since $m$ is continuous on a compact set, it is uniformly continuous, so $\omega_m(\delta)\to0$ as $\delta\downarrow0$. Also, for every $\delta$, $\omega_m(\delta)\leq2\|m\|_\infty$.

On the event $K_n(X_0)>0$, write the tree prediction as the average of $m(X_i)$ over the estimation observations in the query cell, plus the average of their residuals $Y_i-m(X_i)$. The absolute difference between the first average and $m(X_0)$ is at most $\omega_m(D_n(X_0))$. By honesty, conditional on the estimation covariates and the partition, the residuals have conditional mean zero and conditional variances at most $\sigma^2$; they are conditionally independent. Thus the conditional variance of their average is at most $\sigma^2/K_n(X_0)$. On an empty cell, the squared prediction error is $m(X_0)^2\leq\|m\|_\infty^2$. Using $(a+b)^2\leq2a^2+2b^2$, and treating the empty-cell event separately, gives

E[(T_n(X_0)-m(X_0))^2] \leq 2E[\omega_m(D_n(X_0))^2] +2\sigma^2 E\!\left[\frac{\mathbf{1}\{K_n(X_0)>0\}}{K_n(X_0)}\right] +\|m\|_\infty^2P(K_n(X_0)=0).

Each term on the right tends to zero. For the first, $D_n(X_0)\to0$ in probability, so $\omega_m(D_n(X_0))\to0$ in probability; it is bounded by $2\|m\|_\infty$, and hence its squared expectation tends to zero. For the other terms, $K_n(X_0)\to\infty$ in probability implies $P(K_n(X_0)=0)\to0$. It also implies that the bounded random variable $\mathbf{1}\{K_n(X_0)>0\}/K_n(X_0)$ tends to zero in probability, so its expectation tends to zero.

Finally, conditional on the training data, the ideal forest is the expectation of $T_n(x)$ over tree randomization. Jensen's inequality gives $$ (F_n(X_0)-m(X_0))^2 \leq E[(T_n(X_0)-m(X_0))^2\mid\text{training data},X_0]. $$ Taking expectations proves the claim. $\square$

Worked Examples

Worked Example: Shrinking Bins With Growing Occupancy

Let $d=1$, $X\sim\operatorname{Uniform}(0,1)$, and $Y=m(X)+\varepsilon$, where $m$ is continuous and $E[\varepsilon\mid X]=0$, $\operatorname{Var}(\varepsilon\mid X)\leq\sigma^2$. Use a deterministic partition into $k_n=\lfloor n^{1/4}\rfloor$ equal-width intervals. Choose $s_n=\lfloor n^{3/5}\rfloor$ and $q_n=\lfloor s_n/2\rfloor$.

These are integer sample sizes, $s_n\leq n$, $s_n\to\infty$, and $s_n/n\leq n^{-2/5}\to0$. Also $q_n\to\infty$. Every cell has diameter $1/k_n\to0$, so localization holds for every query.

For any query cell, the number of estimation covariates in it has a binomial distribution with parameters $q_n$ and $1/k_n$. Its mean is $$ \frac{q_n}{k_n}\sim \frac{1}{2}n^{3/5-1/4} =\frac{1}{2}n^{7/20}\longrightarrow\infty. $$ The occupancy calculation below shows that the count tends to infinity in probability. Thus the theorem applies: the ideal honest forest formed by averaging these tree predictions is mean-squared consistent.

Worked Example: Turning Expected Leaf Size Into an Inverse-Count Bound

Suppose a partition is independent of the estimation sample, and conditional on the query and its cell, each estimation covariate falls in that cell with probability $p$. Then $K\sim\operatorname{Binomial}(q,p)$. First, $$ P(K=0)=(1-p)^q\leq e^{-qp}. $$ For positive integers $k$, $1/k\leq2/(k+1)$. Moreover, using the binomial expansion, $$ E\!\left[\frac{1}{K+1}\right] =\sum_{k=0}^{q}\frac{1}{k+1}\binom{q}{k}p^k(1-p)^{q-k} =\frac{1-(1-p)^{q+1}}{(q+1)p}. $$ Consequently, $$ E\!\left[\frac{\mathbf{1}\{K>0\}}{K}\right] \leq \frac{2[1-(1-p)^{q+1}]}{(q+1)p} \leq \frac{2}{(q+1)p}. $$ If $qp\to\infty$, both the empty-cell probability and the inverse-count expectation vanish. In the preceding example $p=1/k_n$, and $q_np\sim n^{7/20}/2$, so these bounds verify the required occupancy condition.

Worked Example: Large Leaves Do Not Replace Localization

Let $X\sim\operatorname{Uniform}(0,1)$ and $Y=X$, so $m(x)=x$ and the response noise is zero. Use one cell, $[0,1]$, for every $n$, with $q_n=\lfloor n^{1/2}\rfloor$ estimation observations. The leaf count is always $q_n$, which diverges, but the cell diameter remains $1$.

The tree prediction is the estimation-sample mean $\overline X$, with $E[\overline X]=1/2$ and $\operatorname{Var}(\overline X)=1/(12q_n)$. Since $X_0$ is independent and has mean $1/2$ and variance $1/12$, $$ E[(\overline X-X_0)^2] =\operatorname{Var}(\overline X)+\operatorname{Var}(X_0) =\frac{1}{12q_n}+\frac{1}{12} \longrightarrow\frac{1}{12}. $$ The prediction is not consistent. Occupancy alone controls averaging noise; it cannot remove the error from averaging conditional means across a cell that does not shrink.

Reading the Conditions Carefully

The occupancy condition is about the random query leaf, not merely the average number of observations in the tree or the size of a typical leaf chosen without reference to the query distribution. A tree can have many observations overall while leaving a non-negligible probability that a test point falls in an empty or sparsely populated cell. The theorem requires the count for an independent query to diverge in probability.

Honesty has a separate role. Because the partition is built without the estimation responses, those responses can estimate the conditional mean within the selected cell without having also determined that cell's shape. This makes the conditional noise-averaging argument valid. Honesty alone does not ensure either shrinking cells or enough estimation observations in them.

A common mistake is to reason that a response bound $|Y|\leq M$ automatically gives $|m(x)|\leq M$ everywhere on the cube. It gives that bound only $P_X$-almost surely. If $X=0$ and $Y=0$ almost surely, for example, $m(x)=10x$ is a continuous version of the conditional mean on the cube, although it exceeds $M=1$ away from the support of $X$. The valid global bound used in the proof is $\|m\|_\infty<\infty$, which follows from continuity on the compact cube; it need not be bounded by a response bound.

Key takeaway: A sufficient route to consistency is a growing honest estimation sample, query-leaf occupancy diverging in probability, and query-cell diameter shrinking in probability. Occupancy controls noise, localization controls approximation bias, and honesty supports the conditional averaging argument.

Check Your Understanding

Use the theorem and its proof to answer the following questions.

Why does $K_n(X_0)\to\infty$ in probability imply that the probability of an empty query leaf tends to zero?
In the equal-width-bin example, what are the orders of the cell diameter and the expected query-leaf count?
Which part of the consistency proof uses honesty, and what independence does honesty provide?
Why does the one-cell example remain inconsistent even though its estimation-leaf count diverges?
Why is $\omega_m(\delta)\leq2\|m\|_\infty$ valid even when the support of $X$ does not fill the cube?