Localization Through Shrinking Leaf Diameters

Why Shrinking Cells Matter

A tree predicts at a query point by using observations that share its terminal leaf. The geometry of that leaf therefore determines how far the prediction can reach across the feature space. If the leaf containing a query point remains wide in some direction, it may keep pooling responses from feature values with quite different regression means. If the leaf shrinks around the query, continuity of the regression function makes this source of approximation error small.

The relevant property is geometric localization: the diameter of the query-containing cell tends to zero as the tree becomes more refined. Deep trees do not automatically have this property. What matters is whether splits keep reducing widths in every relevant coordinate, and whether each such split reduces a width by a meaningful amount.

Definition: Let $\mathcal P_n$ be a partition of a feature space in $\mathbb R^d$, and let $C_n(x)$ be the cell of $\mathcal P_n$ containing query point $x$. Its Euclidean diameter is $$ D_n(x)=\operatorname{diam}(C_n(x)) =\sup_{u,v\in C_n(x)}\|u-v\|_2. $$ The cells localize at $x$ if $D_n(x)\to 0$. For random partitions, localization in probability means $D_n(x)\xrightarrow{p}0$; almost-sure localization means $D_n(x)\xrightarrow{a.s.}0$.

Split Counts and Cell Widths

For axis-aligned trees on $[0,1]^d$, a cell is a rectangle. Write $w_j(C)$ for its width in coordinate $j$, and let $N_j(C)$ be the number of splits along the path to $C$ that cut coordinate $j$. A split on another coordinate leaves $w_j(C)$ unchanged. A split on coordinate $j$ is useful for localization when it cuts the current interval away from its endpoints, so neither resulting interval can retain almost all of the original width.

Definition: A split is $\eta$-balanced, for $0<\eta\leq 1/2$, if its cut point lies between fractions $\eta$ and $1-\eta$ of the current interval along the split coordinate. Each child interval on that coordinate then has width at most $1-\eta$ times the parent width.

The following deterministic bound makes the role of split counts explicit.

Result: Suppose an axis-aligned cell starts inside $[0,1]^d$, and every split on coordinate $j$ is $\eta$-balanced. Then $$ w_j(C)\leq (1-\eta)^{N_j(C)} \qquad\text{and}\qquad \operatorname{diam}(C)\leq \left(\sum_{j=1}^d(1-\eta)^{2N_j(C)}\right)^{1/2}. $$

Proof. Initially, each coordinate width is at most $1$. After one balanced split on coordinate $j$, its width is at most $1-\eta$ times its previous width. After $N_j(C)$ such splits, repeated multiplication gives $w_j(C)\leq(1-\eta)^{N_j(C)}$. For a rectangle, the squared Euclidean distance between any two points is at most the sum of the squared coordinate widths. Taking the supremum over pairs of points and then the square root gives the diameter bound. $\square$

Thus, if every coordinate receives a number of balanced splits that diverges, the cell diameter tends to zero. A large total number of splits is not enough by itself: the splits must cover all coordinates.

Worked Example: Cyclic Midpoint Splits

Consider a tree on $[0,1]^2$ that splits at the midpoint of the current interval, alternating between coordinates 1 and 2. After six splits, each coordinate has been split three times. Here $\eta=1/2$, so each width is at most $(1/2)^3=1/8$.

The diameter of the query-containing rectangle is therefore at most $$ \sqrt{(1/8)^2+(1/8)^2} =\frac{\sqrt{2}}{8}\approx 0.177. $$

This bound applies to every query point, regardless of which of the resulting cells contains it. If the same cyclic scheme continues, each coordinate is split an increasing number of times, and the diameter bound converges to zero.

A Random-Split Condition for Localization

A randomized splitting rule can ensure that each coordinate is selected often enough. The next result gives one sufficient condition. It is deliberately stated in terms of pathwise split opportunities: a rule that stops splitting a path early must separately justify that its path depth grows.

Theorem: Consider a sequence of axis-aligned trees whose query path has $L_n$ split levels, with $L_n\to\infty$. Suppose that, conditional on the path and split history before each level, coordinate $j$ is selected with probability at least $p_j>0$. Suppose every split is $\eta$-balanced for a common $\eta>0$. Then the diameter of the query-containing cell converges to zero in probability.

Proof. Let $I_{\ell j}$ equal $1$ if level $\ell$ splits coordinate $j$, and $0$ otherwise. Write $N_j=\sum_{\ell=1}^{L_n} I_{\ell j}$. For $s>0$, the conditional selection-probability assumption gives $$ E[e^{-sI_{\ell j}}\mid\text{history before level }\ell] \leq 1-p_j+p_je^{-s}. $$ Iterating conditional expectations yields $$ E[e^{-sN_j}]\leq(1-p_j+p_je^{-s})^{L_n}. $$ Taking $s=\log 2$, applying Markov's inequality to the event $N_j\leq p_jL_n/2$, and using $1-u\leq e^{-u}$, we obtain $$ P(N_j\leq p_jL_n/2) \leq e^{(\log 2)p_jL_n/2}(1-p_j/2)^{L_n} \leq e^{-p_jL_n(1-\log 2)/2} \leq e^{-p_jL_n/8}. $$ The last inequality holds because $(1-\log 2)/2>1/8$. By the union bound, the probability that any coordinate has fewer than $p_jL_n/2$ splits is at most $\sum_{j=1}^d e^{-p_jL_n/8}$, which tends to zero. On the complementary event, the deterministic width bound gives $$ D_n(x)\leq \left(\sum_{j=1}^d(1-\eta)^{p_jL_n}\right)^{1/2}. $$ This upper bound tends to zero. The probability of the event on which it applies tends to one, proving convergence in probability. $\square$

The conditions are sufficient, not necessary. More generally, the deterministic width result implies localization whenever all coordinate split counts diverge and the reductions in width are strong enough that each coordinate width tends to zero. The random-split condition is a convenient way to ensure this happens with high probability.

Worked Example: Random Coordinate Selection

Suppose a two-dimensional query path has $30$ split levels. At each level, conditional on the previous path, coordinate 1 is selected with probability at least $1/3$, and coordinate 2 with probability at least $2/3$. Assume every split is $1/4$-balanced. The theorem bounds the probabilities of falling below 5 splits on coordinate 1 and 10 on coordinate 2 by $$ P(N_1<5)\leq e^{-30(1/3)/8}=e^{-1.25}, \qquad P(N_2<10)\leq e^{-30(2/3)/8}=e^{-2.5}. $$

Thus, with probability at least $1-e^{-1.25}-e^{-2.5}$, both split counts meet those thresholds. On that event the widths are at most $$ w_1\leq(3/4)^5\approx0.2373, \qquad w_2\leq(3/4)^{10}\approx0.0563. $$ The diameter is consequently at most $$ \sqrt{(3/4)^{10}+(3/4)^{20}}\approx0.244. $$ These finite-depth bounds are not especially tight. The asymptotic point is that as the path depth grows, the probability of insufficient splits tends to zero and both width bounds tend to zero.

Localization Bounds Approximation Bias

Let $m(x)=E[Y\mid X=x]$ be the regression function. For a fixed cell $C$ with $P(X\in C)>0$, define its population leaf prediction as $E[m(X)\mid X\in C]$. This averages the regression function over feature values in the leaf. If $m$ varies little across a small cell, that average must be close to $m(x)$ for a query $x\in C$.

Result: Suppose $m$ is uniformly continuous on the feature space. Define its modulus of continuity by $$ \omega_m(r)=\sup_{\|u-v\|_2\leq r}|m(u)-m(v)|. $$ For any cell $C$ of positive feature probability and any $x\in C$, $$ \left|E[m(X)\mid X\in C]-m(x)\right| \leq \omega_m(\operatorname{diam}(C)). $$

Proof. For every $z\in C$, the definition of diameter gives $\|z-x\|_2\leq\operatorname{diam}(C)$. Hence $|m(z)-m(x)|\leq\omega_m(\operatorname{diam}(C))$. Conditional expectation and the triangle inequality then imply $$ \left|E[m(X)\mid X\in C]-m(x)\right| \leq E[|m(X)-m(x)|\mid X\in C] \leq\omega_m(\operatorname{diam}(C)). $$ This proves the result. $\square$

Uniform continuity means $\omega_m(r)\to0$ as $r\downarrow0$. Therefore, for cells that localize, the population leaf approximation bias vanishes. For a random cell of positive feature probability, the same inequality holds conditional on the cell and query. If $D_n(x)\xrightarrow{p}0$, then $\omega_m(D_n(x))\xrightarrow{p}0$ as well.

The result also gives an expectation bound when $m$ is bounded. Let $M=\sup_x|m(x)|<\infty$. For any $\delta>0$, $$ E[\omega_m(D_n(x))] \leq \omega_m(\delta)+2M\,P(D_n(x)>\delta). $$ Indeed, on $D_n(x)\leq\delta$, monotonicity of the modulus gives the first bound; on the remaining event, the difference between two values of $m$ is at most $2M$. If $D_n(x)\xrightarrow{p}0$, first take $n\to\infty$ and then $\delta\downarrow0$. Both terms tend to zero, so the expected population approximation error also tends to zero.

Worked Example: A Smooth Regression Function on a Small Leaf

Let $X$ be uniform on $[0,1]^2$, let $m(x_1,x_2)=x_1^2+2x_2$, and consider the rectangular leaf $[0.4,0.5]\times[0.3,0.5]$ with query $x=(0.45,0.4)$. The leaf widths are $0.1$ and $0.2$, so its diameter is $\sqrt{0.1^2+0.2^2}=\sqrt{0.05}\approx0.2236$.

The gradient of $m$ is $(2x_1,2)$. On the feature space its norm is at most $2\sqrt{2}$, so the mean-value theorem gives $\omega_m(r)\leq2\sqrt{2}\,r$. The population leaf bias is therefore at most $2\sqrt{2}(0.2236)\approx0.6325$.

The exact values show how conservative this general bound can be. At the query, $m(x)=0.45^2+2(0.4)=1.0025$. Under the uniform distribution conditional on this leaf, $$ E[X_1^2\mid X\in C] =\frac{0.4^2+(0.4)(0.5)+0.5^2}{3} =0.203\overline{3}, \qquad E[2X_2\mid X\in C]=2(0.4)=0.8. $$ Thus the population leaf prediction is $1.003\overline{3}$, and its bias at the query is $1/1200\approx0.000833$. The continuity bound guarantees small error as the diameter shrinks; it need not be sharp for a particular leaf.

From a Leaf Bound to a Forest Bound

An honest forest prediction can be written as a weighted average of observed responses, with nonnegative weights summing to one. When the weights are determined without using the responses being averaged, conditioning on the feature values and weights gives the conditional mean prediction $\sum_i W_i(x)m(X_i)$. If every observation with positive weight lies in a tree leaf containing $x$, then $\|X_i-x\|_2$ is no larger than that leaf’s diameter.

For a single tree with normalized nonnegative weights supported in $C(x)$, the conditional mean prediction consequently satisfies $$ \left|\sum_i W_i(x)m(X_i)-m(x)\right| \leq \sum_i W_i(x)|m(X_i)-m(x)| \leq \omega_m(\operatorname{diam}(C(x))). $$ For a forest, average this inequality across trees and use the triangle inequality. If every tree’s cell diameter is bounded by a common $r$, the forest’s conditional mean approximation error is at most $\omega_m(r)$. More generally, the bound is the weighted average of the individual trees’ modulus bounds.

This argument concerns the approximation of the regression function by localized neighborhoods. It does not, by itself, control the error from having only finitely many responses in a leaf, nor does it establish a full consistency result. Those require additional conditions. Localization addresses a specific but essential part of the analysis: it prevents the prediction from averaging regression means over feature values far from the query.

Common Pitfall

Wrong reasoning: “The tree gets deeper, so its leaves must shrink.” Depth only counts splits. A path could repeatedly split coordinate 1 while leaving coordinate 2 untouched; then its width in coordinate 2 need not decrease at all.
Correction: Track coordinate-wise split counts and the amount by which each split reduces its interval. Localization follows when every relevant coordinate width tends to zero, not merely when total depth increases.
Another limitation: A small cell controls variation in $m$ only when $m$ is suitably continuous. Without such regularity, values of $m$ can differ sharply even at nearby feature points, so the modulus bound need not vanish.

Key takeaway: Balanced splits yield explicit width bounds, and enough such splits in every coordinate force the query leaf to localize. For a uniformly continuous regression function, the population approximation bias—and the corresponding honest forest weighted-mean bias—is then bounded by the function’s modulus of continuity at the leaf diameter.

Check Your Understanding

Use the definitions and bounds above to check your reasoning.

In three dimensions, why does a growing total number of splits fail to guarantee a shrinking query-cell diameter?
A coordinate begins with width at most one and receives four $\eta$-balanced splits. What upper bound does the split-count result give for its final width?
State the condition on the regression function that makes the population leaf bias bound vanish as cell diameter tends to zero.
Why must normalized forest weights be nonnegative for the displayed weighted-mean bound to apply as written?
Does localization alone control the response noise in a finite leaf? Explain what the localization argument does control.