Totally Randomized Versus Response-Guided Forests

Two Routes to Consistency

A partitioning forest predicts by pooling responses from observations that share a terminal cell. Its consistency argument has two parts: the cells must localize near the query point, and the response average within a cell must be sufficiently stable. When the partition is independent of the responses used to estimate those averages, these requirements can be analyzed directly. When responses help choose the partition, the same data can influence both the cells and their averages; the analysis must also control how much the selection can adapt to noise.

We compare these arguments for regression under squared-error loss. Let $X$ take values in a measurable subset of $\mathbb{R}^d$, let $Y$ be a response, and write $m(x)=E[Y\mid X=x]$. Assume $|Y|\leq B$ almost surely, so $|m(x)|\leq B$. For a partition $\mathcal{P}$, estimate $m(x)$ by the average of training responses whose covariates fall in the cell containing $x$, setting the estimate to zero when that cell has no training observations.

Definition: A partition is response-independent for an estimation sample if, conditional on any auxiliary randomness used to construct it, it is independent of that sample’s $(X_i,Y_i)$ pairs. A response-guided partition is one whose construction or selection uses responses. For a cell $A$, its population probability is $p_A=P(X\in A)$, and its diameter is $\sup_{x,z\in A}\|x-z\|$.

Response-independence here is a deliberately clean condition: the partition may be randomized, but its randomness is independent of the estimation sample. Some procedures use covariates to choose splits while keeping split selection independent of the responses; their proofs require conditioning arguments tailored to that sampling scheme. The central contrast remains the same: a response-independent partition does not select its geometry to exploit estimation noise.

Response-Independent Partitions: Localization and Occupancy

For a fixed partition $\mathcal{P}$, define $m_A=E[Y\mid X\in A]$ for every cell with $p_A>0$, and let $m_{\mathcal{P}}(x)=m_A$ when $x\in A$. The difference $m-m_{\mathcal{P}}$ is the approximation error: even with infinitely many observations per cell, the estimator only recovers a cell average. The remaining error comes from estimating those averages with finitely many responses.

Theorem: Suppose $\mathcal{P}$ is independent of an i.i.d. estimation sample of size $n$, has at most $K$ cells, and $|Y|\leq B$. For the cell-average estimator $\hat m_{\mathcal{P}}$, with value zero in an empty cell, $$ E\!\left[\int \bigl(\hat m_{\mathcal{P}}(x)-m(x)\bigr)^2\,dP_X(x)\,\middle|\,\mathcal{P}\right] \leq \int \bigl(m_{\mathcal{P}}(x)-m(x)\bigr)^2\,dP_X(x) +B^2 K\left(\frac{2}{n+1}+\frac{1}{en}\right). $$ Here $P_X$ is the distribution of $X$; cells of probability zero make no contribution.

Proof. Conditional on the partition, let $N_A$ be the number of training covariates in cell $A$. For $p_A>0$, $N_A$ has a binomial distribution with parameters $n$ and $p_A$. Conditional on $N_A>0$, the average of the responses in $A$ has mean $m_A$ and variance at most $B^2/N_A$. If $N_A=0$, its squared difference from $m_A$ is at most $B^2$. Therefore the cell’s expected contribution to the squared error relative to $m_A$, integrated over $A$, is at most $$ B^2p_A\left(E\!\left[\frac{\mathbf{1}\{N_A>0\}}{N_A}\right]+P(N_A=0)\right). $$ For integer $k\geq 1$, $1/k\leq 2/(k+1)$. Also, for $N_A\sim\operatorname{Binomial}(n,p_A)$, $$ E\!\left[\frac{1}{N_A+1}\right] =\frac{1-(1-p_A)^{n+1}}{(n+1)p_A} \leq \frac{1}{(n+1)p_A}. $$ Thus $p_A E[\mathbf{1}\{N_A>0\}/N_A]\leq 2/(n+1)$. Since $(1-p_A)^n\leq e^{-np_A}$ and $u e^{-nu}\leq 1/(en)$ for $u\geq0$, $p_A P(N_A=0)\leq 1/(en)$. Summing over at most $K$ cells gives the stated estimation-error bound. Finally, within each cell, $m_{\mathcal{P}}$ is the conditional mean of $m(X)$, so the cross term between $\hat m_{\mathcal{P}}-m_{\mathcal{P}}$ and $m_{\mathcal{P}}-m$ integrates to zero in expectation. Adding the approximation error proves the result. $\square$

This bound separates the two requirements. If the number of cells $K=K_n$ grows more slowly than $n$, the estimation term vanishes. If $m$ is Lipschitz with constant $L$, and the maximum cell diameter is at most $h_n$, then within each cell $|m(x)-m_A|\leq Lh_n$, so the approximation error is at most $L^2h_n^2$. Shrinking diameters control approximation; adequate occupancy controls estimation.

Worked Example: Equal-Width Randomized Bins

Suppose $X$ is uniform on $[0,1]$, $m$ is Lipschitz with constant $L$, and a response-independent partition divides $[0,1]$ into $K_n=\lceil n^{1/3}\rceil$ equal-width bins. Each cell has diameter $1/K_n$, so its approximation error is at most $L^2/K_n^2$. The theorem gives $$ E\!\left[\int(\hat m_{\mathcal{P}}-m)^2\,dP_X\right] \leq \frac{L^2}{K_n^2} +B^2K_n\left(\frac{2}{n+1}+\frac{1}{en}\right). $$ The first term is at most $L^2n^{-2/3}$. Since $K_n\leq n^{1/3}+1$, the second term is of order $B^2n^{-2/3}$. Both terms vanish, so the integrated prediction error tends to zero. The calculation uses both shrinking cell width and $K_n/n\to0$; either condition alone would not establish this bound’s convergence to zero.

Response-Guided Partitions: Add Complexity Control

With response-guided selection, a small number of cells and small diameters may describe the final partition, but they do not by themselves account for how it was chosen. If many candidate partitions were examined and the one that best fits noisy responses was retained, the selected fit can inherit noise-driven structure. A proof therefore needs a restriction on selection complexity, or a design that separates selection from evaluation.

One transparent option is to construct candidate predictors using one part of the data and choose among them using an independent validation sample. The candidate construction may use responses, but validation responses are not used to create the candidates. For a finite dictionary, the price of selecting among candidates can be bounded explicitly.

Theorem: Conditional on data used to construct $M$ candidate predictors $g_1,\ldots,g_M$, suppose they are fixed measurable functions with $|g_j(x)|\leq B$. Let an independent validation sample of size $v$ consist of i.i.d. pairs with $|Y|\leq B$, and choose $\hat j$ to minimize validation mean squared error. For every $0<\delta<1$, with conditional probability at least $1-\delta$, $$ E[(g_{\hat j}(X)-m(X))^2] \leq \min_{1\leq j\leq M}E[(g_j(X)-m(X))^2] +2B^2\sqrt{\frac{8\log(2M/\delta)}{v}}. $$ The expectations are over a fresh $X$ from the population distribution.

Proof. Conditional on the candidate functions, each squared loss $(Y-g_j(X))^2$ lies in $[0,4B^2]$. Hoeffding’s inequality and a union bound imply that, with probability at least $1-\delta$, every candidate’s validation mean squared loss differs from its population mean squared loss by at most $$ t=B^2\sqrt{\frac{8\log(2M/\delta)}{v}}. $$ Indeed, the probability that any one deviation exceeds $t$ is at most $2\exp(-vt^2/(8B^4))$, so the probability of any such deviation among $M$ candidates is at most $2M\exp(-vt^2/(8B^4))=\delta$. On this simultaneous event, let $j_*$ minimize population loss. Validation minimization and the two deviation bounds give $$ E[(Y-g_{\hat j}(X))^2] \leq \widehat R_{\hat j}+t \leq \widehat R_{j_*}+t \leq E[(Y-g_{j_*}(X))^2]+2t. $$ For any fixed predictor $g$, $E[(Y-g(X))^2]=E[(Y-m(X))^2]+E[(m(X)-g(X))^2]$, because $E[Y-m(X)\mid X]=0$. Subtracting the common irreducible error $E[(Y-m(X))^2]$ proves the claim. $\square$

The bound makes a finite-dictionary complexity condition explicit: $\log M/v\to0$ makes the selection term vanish. The theorem controls selection among candidates; it does not ensure that any candidate is accurate. Localization and occupancy must still make the best candidate’s prediction error small. In settings without a holdout sample, analogous control must come from assumptions or bounds on the complexity of the response-adaptive procedure itself.

Worked Example: Selecting Among Honest Response-Guided Candidates

Suppose a structure sample is used to build $M_n=n^2$ candidate partitions by response-guided split selection. For each candidate, a separate estimation sample of size $s_n$ estimates its cell averages, and an independent validation sample of size $v_n$ selects among the resulting predictors. Suppose every candidate has at most $k_n=\lceil n^{1/4}\rceil$ cells and maximum cell diameter at most $h_n=n^{-1/8}$. Assume the regression function is Lipschitz with constant $L$. Conditional on each selected partition, the response-independent partition bound applies to its separate estimation sample. Thus the best candidate’s expected squared error is bounded by $$ L^2 h_n^2+B^2 k_n\left(\frac{2}{s_n+1}+\frac{1}{e s_n}\right). $$ If $s_n$ and $v_n$ are each proportional to $n$, the approximation term is $L^2n^{-1/4}$, the occupancy term is of order $B^2n^{-3/4}$, and the validation selection term is of order $B^2\sqrt{\log n/n}$, because $\log M_n=2\log n$. All three terms vanish. Response-guided construction is compatible with consistency here because estimation is separated from partition selection, validation controls the finite candidate search, and the candidates localize while keeping their leaf counts small.

Worked Example: When a Complexity Bound Does Not Vanish

Consider the same finite-dictionary validation argument but let $M_v=\lceil\exp(v/16)\rceil$. For fixed $\delta$, $\log(2M_v/\delta)/v$ tends to $1/16$, not zero. Consequently the theorem’s selection term tends to $2B^2\sqrt{8/16}=2B^2/\sqrt{2}$, rather than vanishing. This calculation does not prove that every such dictionary fails; it shows that this bound cannot certify consistency at that growth rate. A proof needs stronger control, a smaller effective candidate class, or another valid argument that prevents response-guided selection from fitting noise.

How to Compare the Arguments

For response-independent partitions, a useful proof template is approximation plus estimation: show that the cells localize enough to approximate $m$, then show the number and occupancy of cells allow their averages to be estimated. For response-guided partitions, those steps are not a complete argument unless the adaptive selection is also controlled. Possible safeguards include sample splitting, explicit restrictions on the candidate class, or a uniform complexity bound appropriate to the procedure. Which safeguard applies depends on how the forest uses responses; independence assumptions should be stated for the actual estimation and selection samples, not inferred from the word “randomized.”

A common mistake is to argue that a response-guided forest is consistent solely because its final leaves shrink and contain enough observations. That reasoning ignores the selection step: the same responses may have been used to search for a partition that makes noisy averages look favorable. The correction is to establish localization and estimation control and justify why adaptive selection does not introduce uncontrolled error. A holdout argument is one clear sufficient route, but its candidate predictors must be fixed before validation and the validation observations must be independent of their construction.

Key takeaway: Response-independent partitions need localization and occupancy conditions for the usual cell-average argument. Response-guided partitions require those conditions plus a valid account of selection complexity, unless independence is restored by the design of the estimation procedure.

Check Your Understanding

Use the distinction between approximation, occupancy, and adaptive selection to answer these questions.

In the response-independent risk bound, what roles do shrinking cell diameters and $K_n/n\to0$ play?
Why does response-guided selection create an additional issue even if the selected partition has few cells?
For the finite-dictionary validation bound, what condition on $M$ and $v$ makes the selection term vanish?
Why must the candidate predictors be fixed independently of the validation responses in the stated proof?
Does a nonvanishing upper-bound term prove that a particular procedure is inconsistent? Explain.

Totally Randomized Versus Response-Guided Forests

What You'll Learn