Why Random Forests Don’t Overfit as Trees Grow: Understanding Convergence in the Random Forest Algorithm

A mathematical and practical guide to Leo Breiman’s Strong Law of Large Numbers proof, the Bias-Variance decomposition, Out-of-Bag (OOB) error stabilization, and Python implementation.

---

A single deep decision tree is notorious for high variance: left unconstrained, it memorizes training noise and generalizes poorly. Yet, combining hundreds of these unstable trees into a Random Forest produces an ensemble whose generalization error stabilizes rather than explodes as the number of trees approaches infinity.

Understanding convergence in the Random Forest algorithm requires distinguishing between two mathematical concepts:

• Ensemble Convergence (B → ∞): What happens to the generalization error as the number of trees B increases for a fixed training dataset of size n.
• Statistical Consistency (n → ∞): Whether the Random Forest converges to the true underlying regression function or Bayes optimal classifier as the sample size n grows to infinity.

This article breaks down the mathematics of Random Forest convergence, derives the variance-reduction limit, explains how to determine the optimal number of trees using Out-of-Bag (OOB) error, and demonstrates convergence empirically in Python.

---

1. Architecture of the Random Forest Ensemble

Given a training dataset D = {(x₁, y₁), …, (x_n, y_n)} drawn independently and identically distributed (i.i.d.) from a joint distribution P(X, Y), a Random Forest constructs B decision trees {h(x, Θ₁), …, h(x, Θ_B)}.

Here, Θ_b represents an i.i.d. random vector governing two sources of stochasticity for the b-th tree:

1. Bootstrap Resampling (Bagging): Selecting n observations with replacement from D.
2. Feature Subspacing: Selecting a random subset of m_try ≤ p features at each node split.

For regression, the ensemble prediction is the unweighted average across all B trees, while for classification, it is the majority vote:

Regression:   f̂_B(x) = (1 / B) ∑_b=1^B h(x, Θ_b)

Classification:   Ĉ_B(x) = arg max_c (1 / B) ∑_b=1^B 핀(h(x, Θ_b) = c)

---

2. Breiman’s Convergence Theorem (As B → ∞)

In his seminal 2001 paper, Leo Breiman proved that Random Forests do not overfit as more trees are added. Instead, the generalization error converges almost surely to a finite limit.

The Margin Function

For a classification problem with true label Y and input vector X, define the margin function of a finite forest of B trees as the difference between the proportion of votes for the correct class and the maximum proportion of votes for any incorrect class:

mr_B(X, Y) = (1 / B) ∑_b=1^B 핀(h(X, Θ_b) = Y) − max_{j ≠ Y} (1 / B) ∑_b=1^B 핀(h(X, Θ_b) = j)

A positive margin (mr_B(X, Y) > 0) indicates a correct classification, while a negative margin indicates a misclassification. The generalization error of the forest is the probability of a negative margin: PE_B^* = P_X,Y(mr_B(X, Y) < 0).

Application of the Strong Law of Large Numbers (SLLN)

Because the random vectors Θ₁, Θ₂, …, Θ_B are conditionally i.i.d. given the training data D, the Strong Law of Large Numbers guarantees that as B → ∞, the empirical average over trees converges almost surely (a.s.) to the expectation over the parameter space Θ:

lim_B→∞ PE_B^* →^a.s. P_X,Y( P_Θ(h(X, Θ) = Y) − max_{j ≠ Y} P_Θ(h(X, Θ) = j) < 0 )

Furthermore, Breiman established an upper bound on this limiting generalization error PE^* in terms of two fundamental properties of the trees:

PE^* ≤ ρ̄(1 − s²) / s²

• Strength (s): The expected margin across the distribution of (X, Y), measuring how accurate the individual trees are on average.
• Correlation (ρ̄): The average correlation between the raw margin functions of two trees drawn with independent Θ and Θ′.

Lowering the correlation ρ̄ (via feature subspacing m_try) while maintaining high individual tree strength s drives down the asymptotic error ceiling.

---

3. Variance Convergence in Regression Forests

For regression, convergence is clearest through the variance of the ensemble average. Suppose each randomized tree has variance Var(h(x, Θ_b)) = σ² and any pair of distinct trees has pairwise correlation ρ.

The variance of the ensemble prediction f̂_B(x) is:

Var(f̂_B(x)) = ρσ² + ((1 − ρ) / B)σ²

Taking the limit as the number of trees approaches infinity (B → ∞):

1. The second term ((1 − ρ) / B)σ² vanishes to 0 at a Monte Carlo rate of 풪(1 / B). This represents the algorithmic variance injected by bootstrap sampling and random feature splits.
2. The first term ρσ² remains constant regardless of how many trees are added. This is the irreducible ensemble variance governed by tree correlation ρ and training sample size n.

Convergence Type	Asymptotic Limit	Mathematical Driver	Practical Implication
Algorithmic Convergence	B → ∞ (Fixed n)	Strong Law of Large Numbers (SLLN) over Θ	Adding trees stabilizes predictions at rate 풪(1/B); never causes iterative overfitting
Variance Floor	limB→∞ Var = ρσ2	Pairwise tree correlation ρ controlled by mtry	More trees cannot eliminate correlation between trees; tuning mtry is required
Statistical Consistency	n → ∞ (L2 Bayes Risk)	Leaf size kn → ∞ and kn / n → 0 (Scornet et al., 2015)	Unpruned trees can overfit noisy data unless tree depth or leaf size is regularized

---

4. Algorithmic Convergence vs. Statistical Consistency (B → ∞ vs. n → ∞)

A common misconception is that “Random Forests cannot overfit.” Mathematically, adding more trees (B → ∞) does not cause overfitting, unlike boosting algorithms (such as AdaBoost or Gradient Boosting) where excessive iterations degrade test error.

However, the limiting infinite forest (B = ∞) trained on a noisy dataset of size n can still overfit the dataset itself if the individual trees are grown to full depth (min_samples_leaf = 1). As demonstrated by Biau (2012) and Scornet, Biau, and Vert (2015), achieving L² statistical consistency (converging to the true regression function f(x) = 피[Y ∣ X = x] as n → ∞) requires controlling tree complexity so that the number of terminal nodes grows slower than the sample size n.

---

5. Monitoring Convergence in Practice via Out-of-Bag (OOB) Error

Because each bootstrap sample draws n observations with replacement, the probability that a specific observation i is excluded from a given tree b is:

P(i ∉ Bootstrap_b) = (1 − 1 / n)ⁿ → e⁻¹ ≈ 0.3679   (as n → ∞)

Roughly 36.8% of the training instances are left out of each tree. By aggregating predictions for each point i exclusively across the trees where i was Out-of-Bag, the OOB error curve provides an unbiased, cross-validated trajectory of ensemble convergence without requiring a separate validation split.

Python Implementation: Tracking OOB Error Stabilization

Using warm_start=True in scikit-learn allows incremental tree additions to inspect the exact point where the OOB error plateaus:

import numpy as np
from sklearn.datasets import make_classification
from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import log_loss

# 1. Generate synthetic classification dataset
X, y = make_classification(
    n_samples=2000, n_features=25, n_informative=15,
    n_redundant=5, flip_y=0.1, random_state=42
)

# 2. Initialize Random Forest with warm_start=True and oob_score=True
rf = RandomForestClassifier(
    warm_start=True,
    oob_score=True,
    max_features="sqrt",
    random_state=42,
    n_jobs=-1
)

# 3. Track OOB error across increasing ensemble sizes B
tree_Steps = range(10, 501, 10)
oob_errors = []

for n_trees in tree_Steps:
    rf.set_params(n_estimators=n_trees)
    rf.fit(X, y)
    oob_error = 1.0 - rf.oob_score_
    oob_errors.append(oob_error)

# 4. Identify empirical convergence point (where rolling change < tol)
diffs = np.abs(np.diff(oob_errors))
converged_idx = np.where(diffs < 0.0005)[0][0]
print(f"OOB Error at B=10   : {oob_errors[0]:.4f}")
print(f"OOB Error at B=500  : {oob_errors[-1]:.4f}")
print(f"Stabilization Point : ~{list(tree_Steps)[converged_idx]} trees")

---

6. Practical Guidelines for Hyperparameter Tuning

1. Setting n_estimators (B): Because error decreases at rate 풪(1 / B), returns diminish rapidly past 200–500 trees. Choose B where the OOB error variance flattens out.
2. Lowering the Asymptotic Floor via max_features (m_try): If the OOB curve plateaus at an unacceptably high error, adding more trees will not help. Tune max_features (to reduce tree correlation ρ) and min_samples_leaf (to prevent individual trees from fitting noise).
3. Class Imbalance and Rare Events: When predicting rare probabilities, require a larger B so that every minority-class sample receives a sufficient number of Out-of-Bag evaluations (typically B ≥ 500).