Finite-Sample Risk Bounds for Honest Forests

Why a Finite-Sample Bound Needs Three Terms

A forest prediction can be inaccurate for different reasons. A tree may average responses from covariate points whose regression means differ from the test point’s mean; this is partition approximation error. Even if the relevant mean is represented well, only finitely many noisy responses may contribute to a leaf; this creates leaf estimation variance. Finally, a practical forest averages a finite number of randomized trees, rather than every possible tree; this adds Monte Carlo error.

Separating these sources is useful because they require different remedies. Better localization can reduce approximation error, more estimation observations per leaf can reduce the effect of response noise, and more trees can reduce Monte Carlo error. A finite-sample bound makes this separation precise without claiming that any one term is automatically small.

Setup and Assumptions

Let \(X\) be an independent test covariate, and let its regression function be \(m(x)=E[Y\mid X=x]\). The estimation sample has covariates \(X_1,\ldots,X_n\) and responses \(Y_i=m(X_i)+\varepsilon_i\). The partition is built honestly: conditional on its construction information, the estimation responses do not determine the prediction weights. We allow the partition to use separate structure data, including responses from that data.

For a test point \(x\), write the prediction from one randomized tree as a weighted average \(T(x;Y,U)=\sum_{i=1}^n W_i(x;U)Y_i\), where \(U\) denotes that tree’s randomization. Assume the weights are nonnegative and sum to one. They can, for example, be equal weights on the estimation observations in the same leaf as \(x\). Assume every tree uses the same estimation sample, and the randomizations for different trees are independent and identically distributed conditional on the data and construction information.

The conditioning in these assumptions matters. Honesty prevents the estimation responses from choosing the weights, but it does not by itself imply that an error’s conditional variance stays bounded after conditioning on every covariate and on the structure information. We will return to this distinction in a worked example.

Let \(\bar W_i(x)=E_U[W_i(x;U)\mid\mathcal G]\) be the mean weight across randomized trees. The infinite-tree prediction for a fixed estimation sample is \(\sum_i\bar W_i(x)Y_i\). For \(B\) trees, let \(F_B(x)=B^{-1}\sum_{b=1}^B T(x;Y,U_b)\).

A Finite-Sample Risk Bound

The risk here is squared prediction error, averaged over the test covariate, estimation sample, partition construction, estimation errors, and tree randomizations. No asymptotic limit or rate condition is needed for the following result.

The first term is the approximation error induced by the forest’s mean partition weights. The second bounds the noise remaining in the infinite-tree prediction. The last term is the finite-tree contribution. The last bound is deliberately general; when the conditional variance of a tree prediction can be calculated or bounded more sharply, it can replace \(M^2\).

Proof of the Decomposition

Fix \(\mathcal G\) and the estimation responses. Conditional on these quantities, the \(B\) tree predictions are independent, have common mean \(\sum_i\bar W_i(X)Y_i\), and have common variance \(\operatorname{Var}_U\{T(X;Y,U)\mid Y,\mathcal G\}\). Thus the conditional mean squared deviation of their average from that common mean is the single-tree variance divided by \(B\). The deviation has conditional mean zero, so its cross-product with the difference between the common mean and \(m(X)\) has conditional expectation zero. Consequently, \[ E_U[\{F_B(X)-m(X)\}^2\mid Y,\mathcal G] = \left\{\sum_i\bar W_i(X)Y_i-m(X)\right\}^2 +\frac{1}{B}\operatorname{Var}_U\{T(X;Y,U)\mid Y,\mathcal G\}. \]

Now condition on \(\mathcal G\). The weights \(\bar W_i(X)\) and the values \(m(X_i)\) are fixed under this conditioning. Substituting \(Y_i=m(X_i)+\varepsilon_i\), the infinite-tree prediction error is the sum of \(a(X)=\sum_i\bar W_i(X)m(X_i)-m(X)\) and \(\sum_i\bar W_i(X)\varepsilon_i\). The latter has conditional mean zero. Expanding its conditional second moment gives \[ E\left[\left\{\sum_i\bar W_i(X)\varepsilon_i\right\}^2\middle|\mathcal G\right] = \sum_i\bar W_i(X)^2 E[\varepsilon_i^2\mid\mathcal G] + \sum_{i\ne j}\bar W_i(X)\bar W_j(X)E[\varepsilon_i\varepsilon_j\mid\mathcal G]. \] The cross-moment assumptions make the second sum zero. The conditional variance is therefore at most \(\sigma^2\sum_i\bar W_i(X)^2\). This proves the first two terms of the stated bound.

Finally, nonnegative weights summing to one imply \(|T(X;Y,U)|\leq M\). Hence \(\operatorname{Var}_U\{T(X;Y,U)\mid Y,\mathcal G\}\leq E_U[T(X;Y,U)^2\mid Y,\mathcal G]\leq M^2\). Substituting this inequality into the exact decomposition proves the result. \(\square\)

Worked Examples

Using the Bound and Avoiding a Common Pitfall

The bound is finite-sample and makes no promise that its terms vanish. The first term depends on how the forest’s average weights place mass on estimation observations whose regression means resemble \(m(X)\). The second depends on the concentration of those weights as well as the conditional noise level: if the weights are equal on \(N\) observations, their squared sum is \(N(1/N)^2=1/N\). The third term can be reduced by increasing \(B\), while leaving the first two terms unchanged.

A common mistake is to condition on estimation covariates to treat the weights as fixed, then use only a variance bound conditioned on each individual covariate. That step is not valid when errors are heteroskedastic and their conditional variances depend on other covariates that also affect the weights. The correction is to state a bound conditional on the full information determining the weights, as in the theorem, or to establish separately that the sampling and independence conditions imply such a bound. One must also account for conditional cross-moments unless conditional independence or another suitable condition rules them out.

The decomposition is useful as an audit: it identifies which part of a proposed argument needs a localization claim, which needs a conditional noise assumption, and which is solely due to using finitely many trees. It does not replace those assumptions with honesty, nor does it turn a finite-sample inequality into a convergence or rate result.