Towards Convergence Rate Analysis of Random Forests for Classification

Wei Gao, Zhi-Hua ZhouNeurIPS 2020 · OpenReview

TL;DR

While Random Forests (RF) are a staple in classification tasks, their theoretical convergence rates have long remained a mystery compared to their regression counterparts. This paper provides the first finite-sample convergence rates for several RF variants, demonstrating that data-dependent splitting mechanisms can push these models toward the theoretical minimax optimal rate.

The Problem: From Consistency to Convergence

In machine learning theory, "consistency" guarantees that an algorithm will eventually find the correct answer given infinite data. However, "convergence rates" provide a much more practical metric: how fast the algorithm gets there.

For Random Forests, most theoretical breakthroughs have historically focused on regression. While it has been known that RFs are consistent for classification, the field has lacked precise "finite-sample rates"—mathematical guarantees of how the error shrinks as the number of training examples ($n$) increases. This paper addresses this critical gap, specifically examining how different splitting mechanisms (the rules trees use to partition the data space) affect the speed of learning in binary classification.

Methods: Analyzing Three Forest Variants

To isolate the impact of different tree-building strategies, the authors analyze three distinct flavors of Random Forests:

  1. Pure Random Forests: Trees where the split dimensions and positions are chosen completely at random, entirely independent of the data labels.
  2. Pure RF with Midpoint Splitting: A variation where the split occurs exactly at the midpoint of a chosen side. This structural change helps shrink the "diameter" of the data cells more efficiently.
  3. Simplified Breiman’s RF: A variant closer to Leo Breiman's original 2001 algorithm. It uses a data-dependent stopping criterion (a cell is only split if it contains different labels) and prioritizes splitting along the longest side of a cell.
Algorithm for the simplified variant of Breiman's random tree

Crucially, the authors first prove a "Bridge Lemma" (Lemma 1). This lemma establishes that the convergence rate of an entire forest is no more than twice the rate of an individual tree, allowing the authors to focus their complex mathematical analysis on single trees before generalizing to the ensemble.

(Note: As a purely theoretical paper, the analysis is conducted under the mathematical assumption that the conditional probability of a class is L-Lipschitz. This ensures the "truth" changes smoothly across the feature space, preventing erratic behavior that would make theoretical learning bounds impossible to establish.)

Key Insights

  • The Power of the Midpoint: The authors show that simply moving from purely random split positions to midpoint splits significantly improves the convergence rate. Intuitively, midpoint splits "box in" the data more rapidly, reducing the diameter of the leaf nodes faster.
  • Data-Dependence is Key: The "Simplified Breiman" variant performs significantly better than the "Pure" versions. By incorporating a stopping rule (halting splits on "pure" nodes), the algorithm reaches a near-minimax rate. This suggests that the empirical success of real-world RFs is heavily tied to these data-dependent mechanisms.
  • Beating the Curse of Dimensionality: Under certain "structural data" assumptions (e.g., when classes are separable by a hyperplane), the authors found a rate of $O(\sqrt{\ln n / n})$. Remarkably, this rate is independent of the dimension ($d$), offering a theoretical explanation for why RFs often perform exceptionally well in high-dimensional spaces.
  • Height Matters: The paper provides a tighter estimate on the maximum height of random trees than previous literature, which serves as a critical component in calculating the final error bounds.

Key Results

The paper establishes the following convergence rates (where $n$ is the number of samples and $d$ is the number of features):

  • Pure RF: $O(n^{-1/(8d+2)})$
  • Pure RF (Midpoint): $O(n^{-1/(3.87d+2)})$ — A clear mathematical improvement over purely random splits.
  • Simplified Breiman RF: $O(n^{-1/(d+2)}(\ln n)^{1/(d+2)})$ — This approaches the minimax rate ($O(n^{-1/(d+2)})$), which is the theoretical speed limit for any classifier under these specific assumptions.
  • Structural Data: $O(\sqrt{\ln n / n})$ — A dimension-independent rate for specific data geometries.

Limitations and Future Work

While a significant step forward, the paper outlines several boundaries to its current findings:

  • Binary vs. Multi-class: The current proofs focus strictly on binary classification. Extending these bounds to multi-class scenarios requires a significantly more complex analysis of "margin" boundaries.
  • Simplified Splitting: The "Simplified Breiman" variant, while closer to practice, still abstracts away the complexity of the original algorithm, which uses Information Gain or Gini Impurity to select the optimal split. Analyzing those specific heuristics remains an open challenge.
  • Bootstrap Sampling: The analysis assumes trees are built on the full dataset or simple random subsamples. The original RF algorithm utilizes bootstrapping (sampling with replacement), the theoretical impact of which is left for future study.

Summary updated

Abstract

Random forests have been one of the successful ensemble algorithms in machine learning. The basic idea is to construct a large number of random trees individually and make prediction based on an average of their predictions. The great successes have attracted much attention on the consistency of random forests, mostly focusing on regression. This work takes one step towards convergence rates of random forests for classification. We present the first finite-sample rate O(n^{-1/(8d+2)}) on the convergence of pure random forests for classification, which can be improved to be of O(n^{-1/(3.87d+2)}) by considering the midpoint splitting mechanism. We introduce another variant of random forests, which follow Breiman's original random forests but with different mechanisms on splitting dimensions and positions. We get a convergence rate O(n^{-{1}/(d+2)}(\ln n)^{{1}/(d+2)}) for the variant of random forests, which reaches the minimax rate, except for a factor (\ln n)^{{1}/(d+2)}, of the optimal plug-in classifier under the L-Lipschitz assumption. We achieve tighter convergence rate O(\sqrt{\ln n/n}) under proper assumptions over structural data.
BibTeX
@inproceedings{gao2020towards,
  author = {Wei Gao and Zhi-Hua Zhou},
  title = {{Towards Convergence Rate Analysis of Random Forests for Classification}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=RYQ91M6nIvU},
}
Figure