Subsample Size and Number of Trees

Two Sources of Error, Two Tuning Choices

A finite forest can make prediction errors for two distinct reasons. Even after averaging infinitely many randomized trees, the resulting predictor may differ from the regression function; this is statistical error. With only a finite number of trees, the random average also fluctuates around that infinite-forest predictor; this is Monte Carlo error. Subsample size and number of trees therefore play different roles: subsample size changes the forest being estimated, while the number of trees controls how accurately its randomized average is computed.

The distinction matters when interpreting a forest that performs poorly. Adding trees can reduce Monte Carlo error, but it cannot remove the statistical error of the infinite forest at the chosen subsample size. Conversely, changing the subsample size may change the statistical error and the amount of tree-to-tree random variation. There is no universal rule that statistical error decreases monotonically with subsample size; that depends on the sampling and tree-building procedure.

Definition: Let $D_n$ be the training data of size $n$, and let $T_{s,\Theta}(x;D_n)$ be a randomized tree prediction at $x$, built using subsample size $s$. The random variable $\Theta$ represents the tree’s random choices, including subsampling. Define the infinite-forest prediction by $m_{n,s}(x;D_n)=E_\Theta[T_{s,\Theta}(x;D_n)\mid D_n]$. For $B$ trees drawn independently conditional on $D_n$, the finite-forest prediction is $F_{n,s,B}(x)=B^{-1}\sum_{b=1}^B T_{s,\Theta_b}(x;D_n)$.

Let $m(x)=E[Y\mid X=x]$ be the regression function, and take a fresh test covariate $X$ independent of the training data and tree randomization. We measure prediction error by expected integrated squared error, averaging over the training data, test covariate, and tree randomization. The definitions below require finite second moments. Conditional independence of the $B$ tree randomizations is essential; the trees share the training data, but their random choices are drawn independently given that data.

Definition: The statistical error at subsample size $s$ is $A_{n,s}=E_{D_n,X}[(m_{n,s}(X;D_n)-m(X))^2]$. The one-tree conditional Monte Carlo variance is $C_{n,s}=E_{D_n,X}[\operatorname{Var}_\Theta(T_{s,\Theta}(X;D_n)\mid D_n,X)]$. Both quantities can depend on $s$; only $B$ is the number of trees.

The Exact Error Decomposition

The key identity separates the infinite-forest statistical error from the extra error caused by using only $B$ trees. It is exact under the definitions above; it is not an approximation or a large-sample bound.

Theorem: If $E[(T_{s,\Theta}(X;D_n))^2]$ and $E[m(X)^2]$ are finite, and the tree randomizations are conditionally independent and identically distributed given $D_n$, then $$ E[(F_{n,s,B}(X)-m(X))^2]=A_{n,s}+\frac{C_{n,s}}{B}. $$

Proof. Write $M=m_{n,s}(X;D_n)$. Conditional on $D_n,X$, each tree prediction has mean $M$, and the conditional mean of their average is also $M$. Expand the squared error around that conditional mean:

(F_{n,s,B}-m(X))^2 =(M-m(X))^2+2(M-m(X))(F_{n,s,B}-M)+(F_{n,s,B}-M)^2.

The conditional expectation of the middle term is zero because $E[F_{n,s,B}-M\mid D_n,X]=0$. Conditional independence gives

\operatorname{Var}(F_{n,s,B}\mid D_n,X) =\frac{1}{B^2}\sum_{b=1}^{B}\operatorname{Var}(T_{s,\Theta_b}\mid D_n,X) =\frac{1}{B}\operatorname{Var}_\Theta(T_{s,\Theta}\mid D_n,X).

Taking expectations, the first squared term becomes $A_{n,s}$, and the conditional variance term becomes $C_{n,s}/B$. This proves the identity. $\square$

If the test response satisfies $Y=m(X)+\varepsilon$, with $E[\varepsilon\mid X]=0$, is independent of the fitted predictor conditional on $X$, and has finite variance, then expected squared prediction error for $Y$ equals $E[\varepsilon^2]$ plus the displayed error. The noise term is irreducible and does not depend on $s$ or $B$. Thus the decomposition also describes the excess prediction error above this noise floor.

Worked Example: Subsample Means Show the Two Terms Exactly

Suppose $Y_1,\ldots,Y_n$ are independent with mean $\mu$ and variance $\sigma^2$. A randomized “tree” selects a uniformly chosen subset of $s$ observations without replacement and predicts their sample mean. Here the target is the constant $\mu$, so $X$ can be omitted. Let $\bar Y$ be the full-sample mean and let $S^2=(n-1)^{-1}\sum_{i=1}^n(Y_i-\bar Y)^2$.

Averaging the subset mean over all size-$s$ subsets gives $\bar Y$: each observation appears in the same fraction $s/n$ of subsets, so its average coefficient is $1/n$. Therefore the infinite-forest statistical error is

A_{n,s}=E[(\bar Y-\mu)^2]=\operatorname{Var}(\bar Y)=\frac{\sigma^2}{n}.

Conditional on the data, the variance of the mean of a uniform size-$s$ subset is $(1-s/n)S^2/s$. Since $E[S^2]=\sigma^2$, this gives $C_{n,s}=\sigma^2(1/s-1/n)$. Hence the finite-forest error is

\frac{\sigma^2}{n}+\frac{\sigma^2(1/s-1/n)}{B}.

For $n=100$, $s=10$, $B=20$, and $\sigma^2=4$, the statistical error is $4/100=0.04$. The one-tree conditional variance averaged over data is $4(1/10-1/100)=0.36$, so the Monte Carlo contribution is $0.36/20=0.018$. The total is $0.058$. If $s=100$, every tree uses the full data and the Monte Carlo term is zero. In this example, increasing $B$ cannot reduce the $0.04$ statistical floor.

How the Two Tuning Choices Interact

For fixed $n$ and $s$, increasing $B$ reduces the Monte Carlo term in inverse proportion to $B$, while leaving $A_{n,s}$ unchanged. To make the total error at most a target $\delta$, the exact decomposition requires $A_{n,s}<\delta$ and

B\geq \frac{C_{n,s}}{\delta-A_{n,s}}.

When $A_{n,s}$ is close to the target, the denominator is small, so many trees may be needed to reach that target. If $A_{n,s}\geq\delta$, no finite number of trees can achieve it at that subsample size. This is the statistical error floor in operational form.

The subsample size can change both terms. It changes which data enter each tree and may change the infinite-forest prediction, hence $A_{n,s}$. It also changes the distribution of randomized trees and hence $C_{n,s}$. The direction and magnitude of those changes are properties of the particular forest construction and data distribution; the decomposition alone does not imply that larger subsamples are always better or that $C_{n,s}$ always decreases.

Worked Example: A Specified Tradeoff for Subsample Size

To see how choosing $s$ can be separated from choosing $B$, suppose a particular procedure has the following illustrative error quantities for $1\leq s\leq n$: $A_{n,s}=(s/n)^2+1/s$ and $C_{n,s}=1$. These are stipulated quantities for this example, not a universal forest rate. With $n=1000$, compare $s=20$ and $s=80$.

At $s=20$, the statistical error is $(20/1000)^2+1/20=0.0004+0.05=0.0504$. At $s=80$, it is $(80/1000)^2+1/80=0.0064+0.0125=0.0189$. In this specified model, the larger subsample lowers the statistical error. With $B=100$, the Monte Carlo contribution is $1/100=0.01$ at either subsample size, so the total errors are $0.0604$ and $0.0289$, respectively.

For this same model, treating $s$ as continuous, the derivative of $A_{n,s}$ is $2s/n^2-1/s^2$. Setting it to zero gives $2s^3=n^2$, or $s=(n^2/2)^{1/3}$, approximately $79.4$ for $n=1000$. The calculation illustrates a possible statistical tradeoff; it does not establish this rate or optimum for other forest procedures. Once $s$ is selected, $B$ can then be increased to make the Monte Carlo term small relative to the resulting statistical error.

Dominance Regimes and Joint Limits

The relative size of $A_{n,s}$ and $C_{n,s}/B$ determines which source dominates. Monte Carlo error dominates when $C_{n,s}/B$ is much larger than $A_{n,s}$; the sources are balanced when they are of similar order; and statistical error dominates when $C_{n,s}/B$ is much smaller. These comparisons should be made at the chosen $n$ and $s$, not inferred from the number of trees alone.

Worked Example: Three Tree-Count Regimes

Suppose a sequence of subsample choices has statistical error $A_{n,s_n}=n^{-1/2}$, and its one-tree conditional variance is $C_{n,s_n}=1$. At $n=10{,}000$, the statistical error is $1/\sqrt{10{,}000}=0.01$. If $B=10$, the Monte Carlo term is $1/10=0.1$, ten times the statistical error. If $B=100$, it is $0.01$, exactly balanced with the statistical error. If $B=10{,}000$, it is $0.0001$, one hundredth of the statistical error. The total errors are, respectively, $0.11$, $0.02$, and $0.0101$. The last increase in tree count makes little difference to the total because the statistical term remains $0.01$.

The same distinction gives a precise criterion for joint asymptotic behavior.

Theorem: Along any sequence $(n,s_n,B_n)$ satisfying the decomposition’s assumptions, the expected integrated squared error tends to zero if and only if $A_{n,s_n}\to0$ and $C_{n,s_n}/B_n\to0$. If the tree predictions are uniformly bounded in absolute value by a constant $M$, then $C_{n,s_n}\leq M^2$, so $B_n\to\infty$ is sufficient to make the Monte Carlo term vanish.

Proof. The error is the sum of the two nonnegative terms $A_{n,s_n}$ and $C_{n,s_n}/B_n$. If both tend to zero, their sum tends to zero. Conversely, if their sum tends to zero, each nonnegative term is bounded above by the sum, so each must tend to zero. For the boundedness claim, conditional variance is at most the conditional second moment. Thus $E[\operatorname{Var}_\Theta(T\mid D_n,X)]\leq E[T^2]\leq M^2$, and $C_{n,s_n}/B_n\leq M^2/B_n$. $\square$

When predictions are not uniformly bounded, simply letting $B_n$ grow is not enough as a general argument: the relevant condition is $C_{n,s_n}/B_n\to0$. A growing conditional tree variance could offset a growing tree count. Likewise, even when Monte Carlo error vanishes, consistency still requires the chosen subsample sizes and construction to make $A_{n,s_n}\to0$. Conditions establishing that statistical behavior depend on how the forest localizes and uses observations.

Common Pitfall

Wrong reasoning: “The trees are averaged, so the total forest error is the variance of one tree divided by $B$.” This incorrectly treats data-induced error as if it were independent tree-level noise.
Correction: Conditional averaging reduces only the variation of randomized trees around their conditional mean, giving $C_{n,s}/B$. The infinite-forest predictor still varies with the training data and may still differ from $m(x)$; its error is $A_{n,s}$ and is not divided by $B$.
Wrong reasoning: “A larger subsample must improve the forest.” The decomposition imposes no monotonicity on $A_{n,s}$ or $C_{n,s}$.
Correction: Assess how $s$ changes both terms for the specific forest procedure. Then choose enough trees that Monte Carlo error is small relative to the statistical error of that choice.

Key takeaway: Choose subsample size to control the statistical behavior of the infinite forest, and choose the number of trees to control Monte Carlo error around it. The exact target is $A_{n,s}+C_{n,s}/B$, not a single error term that vanishes merely by adding trees.

Check Your Understanding

Use the decomposition to answer these questions.

Which part of the expected error changes when $B$ increases while $n$ and $s$ are fixed?
If $A_{n,s}=0.02$, $C_{n,s}=0.8$, and the target error is $0.04$, what is the smallest integer $B$ that meets the target?
Why does conditional independence of tree randomizations matter for the $C_{n,s}/B$ term?
Can $B\to\infty$ alone guarantee vanishing error if $A_{n,s}$ does not tend to zero? Explain.
For bounded tree predictions, what condition on $B_n$ ensures the Monte Carlo term vanishes, and what separate condition is still needed for the total error to vanish?