Deriving Forest Rates from Localization

From Localization to Prediction Risk

A forest can predict accurately only if its leaves are local enough to average responses with similar regression means, but a leaf must also contain enough observations for its average to be stable. These requirements pull in opposite directions: smaller leaves reduce approximation error while often increasing sampling variability. A rate derivation makes that trade-off explicit rather than treating “localization” as a guarantee of accuracy by itself.

Consider a regression model $Y=f(X)+\varepsilon$, where $X$ takes values in a subset of $\mathbb{R}^d$, $E[\varepsilon\mid X]=0$, and $\operatorname{Var}(\varepsilon\mid X)\leq \sigma^2$. Assume that $f$ is Hölder smooth of order $\beta\in(0,1]$: for a constant $L$,

|f(x)-f(z)|\leq L\|x-z\|^\beta

for all relevant $x,z$. For squared-error prediction, the regression function $f(x)=E[Y\mid X=x]$ is the target. The excess risk of a predictor $\hat f$, measured on a fresh observation independent of the training data, is

\mathcal{E}(\hat f) =E\!\left[(Y-\hat f(X))^2\right]-E\!\left[(Y-f(X))^2\right] =E\!\left[(\hat f(X)-f(X))^2\right].

The equality follows by expanding the squares and using $E[Y-f(X)\mid X]=0$. Thus, a bound on squared prediction error relative to $f$ is exactly a bound on excess risk.

Definition: For a query point $x$, a tree’s leaf is the partition cell containing $x$. Its diameter is the supremum of $\|u-v\|$ over points $u,v$ in that cell. Its occupancy is the number of estimation observations used in that leaf. In an honest construction, the observations used to form a leaf’s response average are separate from any responses used to choose the partition.

A Localization Bound for Honest Forests

Here is a useful general statement. It applies when the partitioning and subsampling mechanisms do not use the estimation responses whose noise appears in the leaf averages. Conditional on the estimation covariates and the partitions, assume the errors are independent, have conditional mean zero, and have conditional variances at most $\sigma^2$. Suppose every tree used in a forest has at least $m\geq1$ estimation observations in the leaf containing the query $x$. Denote that leaf’s diameter for tree $b$ by $D_b(x)$. A uniform bound $D_b(x)\leq\delta$ gives a particularly simple consequence.

Theorem: Let a forest prediction be the average of $B\geq1$ tree predictions, each of which is the unweighted mean of the responses in its query leaf. If every query leaf has occupancy at least $m$ and diameter at most $\delta$, and $f$ satisfies the Hölder condition above, then $$ E[(\hat f_B(x)-f(x))^2]\leq L^2\delta^{2\beta}+\frac{\sigma^2}{m}. $$ The expectation includes the estimation responses and any partition randomization. The bound also holds after averaging over a fresh query point $X$.

The two terms have different origins. The first is an approximation term: responses in a leaf may have different conditional means from the value at $x$. The second is a sampling term: even if those means were identical, the leaf average contains response noise.

Condition on the covariates and partitions.
For each tree, the query leaf and its training indices are then fixed; only the estimation errors remain random.

Bound the conditional mean error.
Every training covariate in the query leaf is within distance $\delta$ of $x$, so Hölder smoothness bounds the difference between the average regression mean and $f(x)$.

Bound the conditional noise variance.
An average of at least $m$ independent, mean-zero errors has variance at most $\sigma^2/m$.

Proof: Separating Approximation and Sampling

Write the estimation observations used by tree $b$’s leaf as indices $I_b(x)$, and let $N_b(x)=|I_b(x)|$. Conditional on all estimation covariates and partitions, the tree prediction is

\hat f_b(x) =\frac{1}{N_b(x)}\sum_{i\in I_b(x)} f(X_i) +\frac{1}{N_b(x)}\sum_{i\in I_b(x)}\varepsilon_i.

Call the first term $a_b(x)$ and the second $e_b(x)$. Because $X_i$ and $x$ lie in the same cell, $\|X_i-x\|\leq\delta$. Consequently,

|a_b(x)-f(x)| \leq \frac{1}{N_b(x)}\sum_{i\in I_b(x)}|f(X_i)-f(x)| \leq L\delta^\beta.

The forest’s conditional mean is $B^{-1}\sum_{b=1}^B a_b(x)$, so its difference from $f(x)$ is also at most $L\delta^\beta$, by the triangle inequality. For a fixed tree, conditional independence and zero means give

E[e_b(x)^2\mid X_1,\ldots,X_n,\text{partitions}] =\frac{1}{N_b(x)^2}\sum_{i\in I_b(x)}\operatorname{Var}(\varepsilon_i\mid X_i) \leq \frac{\sigma^2}{N_b(x)} \leq \frac{\sigma^2}{m}.

The trees need not have independent errors: they may use overlapping observations. For any real numbers $u_1,\ldots,u_B$, Cauchy–Schwarz gives $(B^{-1}\sum_b u_b)^2\leq B^{-1}\sum_bu_b^2$. Apply this to the tree noise terms and take conditional expectations:

E\!\left[\left(\frac{1}{B}\sum_{b=1}^B e_b(x)\right)^2\middle|X_1,\ldots,X_n,\text{partitions}\right] \leq \frac{1}{B}\sum_{b=1}^B E[e_b(x)^2\mid X_1,\ldots,X_n,\text{partitions}] \leq \frac{\sigma^2}{m}.

The averaged noise has conditional mean zero. Therefore the conditional squared error is its conditional variance plus the squared conditional-mean error, and is at most $L^2\delta^{2\beta}+\sigma^2/m$. Taking expectations over the covariates and partitions proves the result. Integrating the same pointwise bound over the distribution of a fresh $X$ proves the risk version. $\square$

Rates From Diameter and Occupancy

The theorem can be used directly with a geometric localization guarantee and an occupancy guarantee. More generally, if the diameter is random and $E[D_b(X)^{2\beta}]\leq r_n$ for each tree, the same argument with the squared bias bounded by the average of the trees’ squared bias bounds gives

E[(\hat f_B(X)-f(X))^2]\leq L^2r_n+\frac{\sigma^2}{m_n},

provided each relevant occupancy is at least $m_n$. Thus, if $r_n=O(n^{-a})$ and $m_n$ is at least a constant times $n^b$, the excess risk is $O(n^{-a}+n^{-b})$. The slower-decaying term determines the overall rate. This statement does not assert that any particular forest automatically attains those diameter or occupancy rates; they must be established for the construction at hand.

Worked Example: Lipschitz Regression on a Square

Let $X$ be uniform on $[0,1]^2$, let $f(x_1,x_2)=x_1+x_2$, and let $\varepsilon\sim N(0,1)$ independently of $X$. The function is Lipschitz with constant $L=\sqrt{2}$, since $\left|(x_1+x_2)-(z_1+z_2)\right|\leq\sqrt{2}\|x-z\|$. Use square cells of side $h=1/q$. Their diameter is $\delta=\sqrt{2}/q$. In a regular design with $n=q^4$ observations allocated equally across the $q^2$ cells, each cell has occupancy $m=q^2$. The theorem gives

L^2\delta^2+\frac{\sigma^2}{m} =2\left(\frac{\sqrt{2}}{q}\right)^2+\frac{1}{q^2} =\frac{4}{q^2}+\frac{1}{q^2} =5q^{-2}=5n^{-1/2}.

The approximation and variance terms are both of order $n^{-1/2}$. This calculation is conditional on the stated regular occupancy; random designs require a separate argument to justify an occupancy bound.

Worked Example: Rougher Regression in Four Dimensions

Let $X$ be uniform on $[0,1]^4$, let $f(x)=\sqrt{x_1}$, and let $\varepsilon\sim N(0,4)$ independently of $X$. For $a,b\in[0,1]$, $|\sqrt a-\sqrt b|\leq\sqrt{|a-b|}$, so $f$ is Hölder with $\beta=1/2$ and $L=1$. Divide each coordinate into $q$ equal intervals. The cell diameter is $2/q$. With $n=q^5$ observations allocated equally to the $q^4$ cells, occupancy is $m=q$. Therefore,

L^2\delta^{2\beta}+\frac{\sigma^2}{m} =\left(\frac{2}{q}\right)^1+\frac{4}{q} =\frac{6}{q} =6n^{-1/5}.

Here the lower smoothness order changes the approximation term: it scales as diameter to the first power rather than diameter squared. The variance term has the same order under the specified occupancy.

Worked Example: When Approximation Is the Bottleneck

Suppose the response model has $f(x)=2x$ on $[0,1]$, Hölder order $\beta=1$, constant $L=2$, and independent noise $\varepsilon\sim N(0,3)$. Assume a sequence of partitions has query-cell diameter at most $n^{-1/6}$, while every query leaf contains at least $n^{2/3}$ estimation observations. The separate terms are

\text{approximation}\leq 2^2(n^{-1/6})^2=4n^{-1/3}, \qquad \text{sampling variance}\leq 3n^{-2/3}.

Thus the total excess risk is at most $4n^{-1/3}+3n^{-2/3}$, which is $O(n^{-1/3})$. The leaf occupancy is already large enough that further variance reduction does not change the rate unless localization also improves.

Choosing a Localization Scale

A common benchmark expresses cell diameter as proportional to a scale $h$ and occupancy as proportional to $nh^d$. This relation is appropriate only when the design and partition construction actually provide that occupancy, or when a suitable high-probability or expected occupancy result has been proved. Under this relation, the risk bound has the form

R(h)=A h^{2\beta}+\frac{B}{n h^d}, \qquad A>0,\quad B>0,\quad h>0.

The first term increases with cell scale and the second decreases with it. The next derivation identifies the unique minimizing positive scale; it does not rely on convexity.

Result: For $A,B,n,d,\beta>0$, the function $R(h)=A h^{2\beta}+B/(nh^d)$ has a unique minimizer $$ h_*=\left(\frac{Bd}{2\beta A n}\right)^{1/(2\beta+d)}. $$ At this scale, $R(h_*)$ is a constant multiple of $n^{-2\beta/(2\beta+d)}$.

To prove uniqueness, differentiate for $h>0$:

R'(h)=2\beta A h^{2\beta-1}-\frac{Bd}{n}h^{-d-1} =h^{-d-1}\left(2\beta A h^{2\beta+d}-\frac{Bd}{n}\right).

The factor $h^{-d-1}$ is positive. The expression in parentheses is strictly increasing in $h$, because $h\mapsto h^{2\beta+d}$ is strictly increasing, and it changes sign exactly once: it tends to $-Bd/n<0$ as $h$ decreases to zero and tends to infinity as $h$ increases without bound. Hence $R'(h)$ is negative below its unique zero and positive above it. Solving for that zero gives $h_*$, proving it is the unique global minimizer. This argument does not require $R''(h)$ to be positive everywhere.

At the minimizer, the derivative equation also gives

\frac{B}{n h_*^d}=\frac{2\beta}{d}A h_*^{2\beta}.

So the two terms are comparable up to constants depending on $\beta$ and $d$. Since $h_*$ is proportional to $n^{-1/(2\beta+d)}$, the approximation term $h_*^{2\beta}$ is proportional to $n^{-2\beta/(2\beta+d)}$; the variance term has that same order by the displayed relation. This yields the stated rate. If $h$ is restricted to a feasible range, the minimizer is instead the unconstrained value when feasible, or the nearest boundary point otherwise.

Common Pitfall and Practical Interpretation

Using diameter as the whole risk bound. A small diameter controls how much the regression mean varies inside a leaf, but it says nothing by itself about how noisy the leaf average is. Include an occupancy-based sampling term.
Using the full sample size in every leaf’s variance. The relevant denominator is the number of responses actually averaged in that leaf, not automatically $n$. Subsampling or small leaves can make that number much smaller.
Assuming averaging trees removes all sampling variance. Trees may reuse observations, so their errors can be dependent. The theorem’s Jensen bound is valid without independence between trees, but does not promise a $1/B$ variance reduction.
Applying the bound to response-adaptive partitions without justification. The proof conditions on partitions and uses mean-zero estimation errors there. If responses used in the leaf average also influenced partition selection, that conditional argument need not hold. Honesty or another valid dependence argument is needed.

The practical value of a rate derivation is its diagnostic structure. A forest with excellent localization but persistently tiny leaves may be variance-limited; a forest with ample occupancy but coarse leaves may be approximation-limited. To claim a particular rate, establish both ingredients under the actual sampling and partition scheme, then combine them without dropping either term.

Check Your Understanding

Use the assumptions in each question explicitly; a bound on one source of error does not automatically control the other.

If the Hölder order is $\beta$ and the maximum cell diameter is $\delta_n$, what is the order of the approximation contribution in the localization bound?
Why does the forest variance argument remain valid when different trees reuse the same estimation responses?
If $r_n=O(n^{-1/4})$ and occupancy is at least a constant times $n^{1/2}$, what is the resulting excess-risk rate from the general bound?
Under occupancy proportional to $nh^d$, how does the optimal scale depend on $n$, $d$, and $\beta$?
What additional concern arises if the same responses determine both the partition and the leaf average?