A Worked Rate Derivation for Random-Split Forests

Why Derive a Rate for a Specific Split Rule?

A regression-tree rate is not determined by the label “randomized forest” alone. It depends on how the partition localizes a prediction point and how many training observations remain in its leaf. A split rule may create many small-volume leaves while leaving some coordinate directions almost untouched. The resulting cells can have small volume but still be wide, so volume alone does not establish a useful approximation bound.

We work through one explicit model: midpoint splits on a cube, with a fresh coordinate selected uniformly at random at each split. The calculation separates two sources of error. Smoothness of the regression function controls the error from using one leaf to represent nearby points; the number of observations in that leaf controls the error from estimating its mean. The derivation also shows how random coordinate allocation can slow the rate through occasional wide cells.

Model and Assumptions

Definition: Let $X$ be uniform on $[0,1]^d$, and let $Y$ be a response with $|Y|\leq B$ almost surely. Write $m(x)=E[Y\mid X=x]$. Assume the regression function is Hölder smooth of order $0<\beta\leq1$ in the sup norm: for all $x,z\in[0,1]^d$, $|m(x)-m(z)|\leq L\|x-z\|_\infty^\beta$. A depth-$k$ random-split tree starts at the cube and, at each node, bisects that node at its midpoint along a coordinate selected uniformly from $\{1,\ldots,d\}$. Coordinate choices are independent across nodes and independent of the training data. Its prediction at $x$ is the average of training responses in the leaf containing $x$, with prediction zero if that leaf is empty.

The training observations $(X_i,Y_i)$, $i=1,\ldots,n$, are independent copies of $(X,Y)$, and the test point $X_0$ is an independent copy of $X$. We study expected squared prediction error, averaging over the training data, test point, and tree randomization. The bounded-response assumption gives a simple uniform control of leaf estimation error and the empty-leaf case. The uniform design and midpoint splits make every depth-$k$ cell have volume $2^{-k}$.

Worked Example: Cell Geometry Along One Path

Take $d=3$, depth $k=6$, and suppose the coordinates selected along the path to a particular leaf are $1,2,1,3,1,2$. The split counts are $N_1=3$, $N_2=2$, and $N_3=1$, so the cell side lengths are $2^{-3}=1/8$, $2^{-2}=1/4$, and $2^{-1}=1/2$.

The cell volume is $(1/8)(1/4)(1/2)=1/64=2^{-6}$, as required. Its sup-norm diameter is the largest side length, $1/2$. For a Lipschitz regression function ($\beta=1$), the difference between its value at the query point and its average over this cell is at most $L/2$. The small volume $1/64$ therefore does not imply that the cell is narrow in every direction.

Two Contributions to Prediction Error

Fix a test point $x$ and a realized tree, and let $C$ be its leaf. Write $M$ for the number of training predictors in $C$, and $\mu_C=E[Y\mid X\in C]$. If $M>0$, the leaf prediction estimates $\mu_C$ by averaging the responses in the leaf. The target $m(x)$ can differ from $\mu_C$, because the cell contains points other than $x$. The following inequality separates these errors:

(\hat m(x)-m(x))^2 \leq 2(\hat m(x)-\mu_C)^2+2(\mu_C-m(x))^2.

The second term is controlled by the cell diameter. For every $z\in C$, smoothness gives $|m(z)-m(x)|\leq L\operatorname{diam}_\infty(C)^\beta$. Averaging over $X$ conditional on $X\in C$ yields $|\mu_C-m(x)|\leq L\operatorname{diam}_\infty(C)^\beta$. The first term is controlled by occupancy: a leaf with few observations produces a noisy average, and an empty leaf uses the specified fallback prediction.

Worked Example: Leaf Occupancy and Empty-Leaf Probability

Let $n=1000$ and $k=8$. For any fixed query point and realized partition, its leaf has probability $p=2^{-8}=1/256$ under the uniform design. Thus $M\sim\operatorname{Binomial}(1000,1/256)$ conditional on that leaf, and $E[M]=1000/256=3.90625$.

The probability of an empty leaf is $(1-1/256)^{1000}$, which is at most $\exp(-1000/256)=\exp(-3.90625)$, approximately $0.0201$. This is an upper bound, not an equality. A leaf with expected occupancy below four can therefore still be empty with non-negligible probability; the risk calculation must account for this event rather than treating the expected count as an actual count.

Expected Width Under Random Coordinate Splits

Along the path to a fixed query point, let $N_j$ be the number of the $k$ splits assigned to coordinate $j$. The vector of counts has a multinomial distribution with $k$ trials and coordinate probabilities $1/d$. The side length in coordinate $j$ is $2^{-N_j}$, so the cell’s sup-norm diameter is $\max_j 2^{-N_j}$.

For $0<\beta\leq1$, the largest of nonnegative numbers raised to $\beta$ is no larger than their sum raised coordinatewise to $\beta$. Consequently, $\operatorname{diam}_\infty(C)^{2\beta}\leq\sum_{j=1}^d 2^{-2\beta N_j}$. For each $j$, $N_j\sim\operatorname{Binomial}(k,1/d)$. Using the probability generating function of a binomial variable gives the exact expectation of each summand:

E[2^{-2\beta N_j}] =\left(1-\frac{1-2^{-2\beta}}{d}\right)^k.

Define $q=1-(1-2^{-2\beta})/d$, which lies strictly between zero and one. Summing over the $d$ coordinates gives $E[\operatorname{diam}_\infty(C)^{2\beta}]\leq d q^k$. This bound captures the possibility that one coordinate receives unusually few splits; replacing every $N_j$ by its mean would not by itself justify an expectation bound on the largest side length.

Worked Example: A Numerical Width Bound

Take $d=2$, $\beta=1$, and $k=5$. Here $2^{-2\beta}=1/4$, so $q=1-(1-1/4)/2=5/8$. The expected squared sup-norm diameter is bounded by $d q^k=2(5/8)^5=2(3125/32768)$, which is approximately $0.1907$.

The bound is an expectation over the random coordinate sequence along the path. It is not a claim that every depth-five leaf has squared diameter at most $0.1907$. For example, a path that splits only one of the two coordinates has a side of length one and squared sup-norm diameter one. The expectation bound includes such paths as well as more balanced ones.

A Finite-Sample Risk Bound

Theorem: Under the model assumptions above, for every integer $k\geq0$, the depth-$k$ tree satisfies $$ E[(\hat m(X_0)-m(X_0))^2] \leq 2L^2d q^k +2B^2\left\{\frac{2}{(n+1)2^{-k}}+\exp(-n2^{-k})\right\}, \qquad q=1-\frac{1-2^{-2\beta}}{d}. $$

Proof. Conditional on the tree and $X_0=x$, the leaf $C$ is fixed and each training predictor falls in it with probability $p=2^{-k}$. Therefore $M\sim\operatorname{Binomial}(n,p)$. Conditional on $M>0$, the responses in the leaf are independent draws from the response distribution conditional on $X\in C$. Their mean is $\mu_C$, and their variance is at most $B^2$, since $|Y|\leq B$. Thus the conditional mean squared deviation of their average from $\mu_C$, given $M$, is at most $B^2/M$. If $M=0$, the prediction is zero and $|\mu_C|\leq B$, so the squared deviation is at most $B^2$.

For positive integers $M$, $1/M\leq2/(M+1)$. Also, for a binomial random variable,

E\left[\frac{1}{M+1}\right] =\frac{1-(1-p)^{n+1}}{(n+1)p} \leq\frac{1}{(n+1)p}.

The identity follows by writing $\binom{n}{r}/(r+1)=\binom{n+1}{r+1}/(n+1)$ in the binomial sum, then summing over $r=0,\ldots,n$. Moreover, $P(M=0)=(1-p)^n\leq\exp(-np)$. Combining these facts bounds the expected squared deviation from $\mu_C$ by $B^2\{2/((n+1)p)+\exp(-np)\}$.

Apply $(a+b)^2\leq2a^2+2b^2$ with $a=\hat m(X_0)-\mu_C$ and $b=\mu_C-m(X_0)$. The occupancy bound just obtained is multiplied by two. Smoothness bounds the second squared term by $L^2\operatorname{diam}_\infty(C)^{2\beta}$; its expectation over the tree and test point is at most $L^2d q^k$, by the width calculation. Substituting $p=2^{-k}$ proves the displayed inequality. $\square$

The same bound applies to the expected risk of a forest prediction formed by averaging any number of such tree predictions, provided its trees use the stated randomization independently of the data. Conditional on the training data and test point, squared loss of an average is no larger than the average squared loss, by convexity of the square. Averaging that inequality gives the claim; no independence between tree predictions is needed for this step.

Balancing the Terms to Obtain a Rate

The width contribution decreases as $q^k$, while the leading occupancy contribution grows as $2^k/n$. The empty-leaf term decreases exponentially in $n2^{-k}$. To balance the first two terms, choose $k=\left\lfloor\log(n)/\log(2/q)\right\rfloor$, where $\log$ denotes the natural logarithm. This choice is nonnegative for $n\geq1$, since $2/q>1$.

Set $a=-\log(q)/\log(2/q)$, which is positive. The floor choice gives $k\geq\log(n)/\log(2/q)-1$, hence $q^k\leq q^{-1}n^{-a}$. It also gives $k\leq\log(n)/\log(2/q)$, hence $2^k/n\leq n^{-a}$. Finally, $n2^{-k}\geq n^a$, so the empty-leaf contribution is at most $\exp(-n^a)$. For $n\geq1$, $\exp(-n^a)\leq C_a n^{-a}$ for some finite constant $C_a$, because $t\exp(-t)$ is bounded for $t>0$, with $t=n^a$. Thus the theorem yields a constant $C$, depending only on $d,\beta,L,B$, such that

E[(\hat m(X_0)-m(X_0))^2]\leq C n^{-a}, \qquad a=\frac{-\log q}{\log(2/q)}, \qquad q=1-\frac{1-2^{-2\beta}}{d}.

Worked Example: Calculating the Exponent

For $d=2$ and $\beta=1$, $q=5/8$, as above. The exponent is $a=-\log(5/8)/\log(16/5)=\log(8/5)/\log(16/5)$, approximately $0.404$. The selected depth is $k=\lfloor\log(n)/\log(16/5)\rfloor$. For $n=1024$, this gives $k=\lfloor6.931/1.163\rfloor=5$.

This calculation gives a bound of order $n^{-0.404}$, up to a constant under the stated assumptions. It is not the usual smoothness rate for a balanced partition: independent coordinate choices can leave a direction under-split, and the expectation of the width reflects that feature-starvation risk. In dimension one, $q=2^{-2\beta}$, so $a=2\beta/(1+2\beta)$, which is the familiar one-dimensional balance of squared smoothness bias and estimation variance.

Common Pitfall: Confusing Volume with Localization

A common but incorrect argument is: “Every leaf has volume $2^{-k}$, so its diameter must be of order $2^{-k/d}$, and the bias is therefore of that order.” Equal volume does not imply equal side lengths. A two-dimensional cell with side lengths $1$ and $2^{-k}$ has the same volume $2^{-k}$, but its diameter is still one. Random coordinate splits make this issue probabilistic rather than eliminating it: the coordinate counts fluctuate, and wide leaves occur with positive probability.

The correction is to bound the quantity the smoothness assumption actually uses: the cell diameter, not just its volume. Here the multinomial split counts yield an explicit expected-width bound, and the occupancy calculation separately uses the known volume. The derivation also relies on midpoint splits and a uniform design; with nonuniform predictors, a cell’s probability mass need not equal its volume, so the occupancy argument would require a different lower bound on leaf probability. The rate is therefore a conclusion for this specified model, not a rate that follows from randomization alone.

Key takeaway: A worked tree rate requires both geometric localization and enough observations per leaf. For independent uniform coordinate choices, the width term is governed by $q^k$, while the occupancy term is governed by $2^k/n$; balancing them gives the stated smoothness- and dimension-dependent exponent.

Check Your Understanding

Use the stated model and assumptions to answer the following.

For a depth-$k$ midpoint tree, what is the volume of every leaf, and why does that fact alone not determine its diameter?
For fixed $d$ and $\beta$, explain why the expected width bound decreases as $k$ increases.
Which part of the finite-sample risk bound accounts for an empty leaf, and what inequality bounds its probability?
When $d=1$, simplify $q$ and verify the resulting exponent $a$.
Which assumptions would need reconsideration before using this occupancy calculation for a nonuniform predictor distribution?