In machine learning, the "wisdom of the crowd" is a well-worn trope. We know that averaging multiple models—whether through bagging in Random Forests or iterative refinement in Gradient Boosting—usually yields better results than any single model could achieve alone. However, for a long time, our theoretical understanding lagged behind this empirical success. We understood that ensembling reduced variance, but we lacked rigorous proof that an ensemble could fundamentally outpace the convergence limits of its own components.
Recent research has bridged this gap, providing a mathematical foundation for why ensembles are strictly superior to single learners, particularly in regression and density estimation.
The Convergence Gap
The core intuition behind this research direction is the "convergence rate"—the speed at which a model's error decreases as it sees more data. Traditionally, if a single decision tree has a certain theoretical limit on how fast it can learn a smooth function, it was assumed the forest would share that same fundamental limit, even if it was more stable in practice.
However, work by Yuchao Cai, Hanyuan Hang, and colleagues in Boosted Histogram Transform for Regression proved something more radical. They demonstrated that for smooth target functions, a boosted ensemble of histogram transforms achieves a convergence rate that is strictly better than a single base learner. Specifically, they showed that the error upper bound of the ensemble is lower than the error lower bound of an individual component. This means the ensemble isn't just "better" in a vague sense; it operates in a different mathematical league than its parts.
From Trees to Forests: The Averaging Effect
Why does this happen? The answer lies in how the ensemble aggregates information. In Sharp Analysis of a Simple Model for Random Forests, Jason M. Klusowski settled a decade-old question by analyzing the "averaging effect" of the entire forest rather than summing the bounds of individual trees.
By applying Jensen’s inequality to the squared error term, Klusowski showed that the approximation error of a forest is bounded by the expectation of the trees' performance, rather than the average of their individual error bounds. This subtle shift in perspective allows the forest to "smooth out" the approximation errors of individual trees, leading to tighter convergence rates than previously thought possible.
Extending to Unsupervised Density Estimation
While the benefits of ensembling were well-documented in supervised learning (classification and regression), the unsupervised realm of density estimation remained a theoretical frontier. How do you prove that boosting improves a model's ability to estimate a probability distribution?
In GBHT: Gradient Boosting Histogram Transform for Density Estimation, Jingyi Cui and Zhouchen Lin provided the first rigorous proof that boosting enhances base learners in this context. By iteratively combining random histogram transforms using a negative log-likelihood loss, the ensemble achieves superior local adaptivity.
Similarly, Hanyuan Hang and Hongwei Wen explored this in Random Forest Density Estimation. They found that in multi-dimensional spaces ($d \geq 2$), the ensemble of randomized trees overcomes the "curse of dimensionality" and boundary discontinuities that plague traditional methods like Kernel Density Estimation (KDE). The ensemble's ability to split space at randomized midpoints allows it to converge faster than any single partition-based estimator could.
Diversity as Implicit Regularization
The final piece of the puzzle is diversity. If all models in an ensemble are identical, the ensemble provides no benefit. Joachim Schreurs and Johan Suykens explored this in Ensemble Kernel Methods, Implicit Regularization and Determinental Point Processes.
They demonstrated that training "ridgeless" kernel models on small, diverse subsets of data acts as a form of implicit regularization. By using Determinantal Point Processes (k-DPPs) to select these subsets, they ensured the models were sufficiently different from one another. This diversity is particularly effective at reducing error on the "tails" of a dataset—the sparse regions where a single global model usually fails.
Summary of Intuition
The shift in this research area is from seeing ensembles as a way to "fix" weak learners to seeing them as a way to "transcend" them.
- Strict Superiority: Ensembles don't just reduce variance; they achieve faster convergence rates (lower error bounds) than their base learners.
- Collective Smoothing: The forest is mathematically smoother than the tree, a property captured by analyzing the expectation of the ensemble rather than the sum of its parts.
- Dimensionality Resilience: In high-dimensional density estimation, the randomized partitioning of ensembles allows for a level of adaptivity that single-model estimators cannot match.