Abstract
Ensemble learning is a popular technique to improve the accuracy of machine learning models. It traditionally hinges on the rationale that aggregating multiple weak models can lead to better models with lower variance and hence higher stability, especially for discontinuous base learners. In this paper, we provide a new perspective on ensembling. By selecting the most frequently generated model from the base learner when repeatedly applied to subsamples, we can attain exponentially decaying tails for the excess risk, even if the base learner suffers from slow (i.e., polynomial) decay rates. This tail enhancement power of ensembling applies to base learners that have reasonable predictive power to begin with and is stronger than variance reduction in the sense of exhibiting rate improvement. We demonstrate how our ensemble methods can substantially improve out-of-sample performances in a range of numerical examples involving heavy-tailed data or intrinsically slow rates.
Introduction: The Heavy-Tail Challenge
In many real-world domains—including finance, physics, and large-scale language modeling—data distributions often exhibit "heavy tails." In these scenarios, extreme outliers occur far more frequently than predicted by standard Gaussian models. For machine learning practitioners, this poses a significant hurdle: standard training paradigms like Empirical Risk Minimization (ERM) or Sample Average Approximation (SAA) suffer from slow concentration.
Technically, the "excess risk"—the gap between a model's performance and the theoretical optimum—decays at a slow polynomial rate ($n^{-\alpha}$). Consequently, a single "bad" batch of training data containing extreme outliers can catastrophically degrade model performance. While traditional ensemble methods like bagging (averaging models) reduce variance, they typically only improve performance by a constant factor without altering the fundamental rate at which the risk of failure diminishes.
Methods: Mode Estimation via Subsampling
This research proposes a paradigm shift from averaging models to mode estimation—identifying the most likely "optimal" model. The authors introduce two core algorithms:
- MoVE (Majority Vote Ensembling): Tailored for discrete solution spaces, MoVE trains a base learner on multiple small random subsamples and uses a majority vote to select the most frequent model.
- ROVE (Retrieval and $\epsilon$-Optimality Vote Ensembling): Designed for continuous spaces (e.g., neural network weights). ROVE first collects a pool of candidate models from subsampled runs and then uses a second set of subsamples to "vote" for candidates that achieve $\epsilon$-optimal performance on those specific subsets.
The critical innovation is the use of small subsamples ($k \ll n$). By training on subsets, the influence of rare outliers is isolated to a minority of the ensemble, allowing the majority of models to capture the underlying signal effectively.
Key Insight: From Polynomial to Exponential Tails
The most striking theoretical contribution is the proof that subsampled ensembling can transform the generalization tail from polynomial ($1/n$) to exponential ($e^{-n}$). This "tail enhancement" is fundamentally stronger than simple variance reduction.
As shown in Figure 1, the ROVE methods consistently achieve lower costs across various sample sizes. More importantly, the tail probability plots (c and f) demonstrate that the probability of high-cost (poor performance) outcomes drops off much faster for the ensemble methods than for the base learner.
Experimental Results
The authors validated their approach across synthetic regression, real-world UCI datasets, and stochastic programming problems.
Neural Networks and Heavy-Tailed Noise
In settings with heavy-tailed Pareto noise, ROVE significantly outperformed both the base learner and standard bagging. The benefits became more pronounced as model complexity (network depth) increased.
As illustrated in Figure 5, while Bagging provides some improvement over the base learner, the ROVE variants (ROVE and ROVEs) demonstrate superior robustness and lower out-of-sample costs, especially as the noise distribution becomes more extreme (lower Pareto shape).
Decision Trees and Optimization
ROVE also outperformed state-of-the-art ensembles like Random Forests and XGBoost in "high-end tail" scenarios. In stochastic programming, MoVE and ROVE consistently achieved lower out-of-sample costs than standard SAA, particularly in complex optimization problems with multiple optimal solutions.
Conclusion
Subsampled ensembling offers a powerful tool for robust machine learning in the presence of heavy-tailed data. By focusing on the "mode" of the model distribution rather than the mean, these methods provide exponential tail guarantees that traditional ensembling cannot match. Future work may involve integrating these techniques into the training of Large Language Models (LLMs) to better handle the inherently heavy-tailed nature of web-scale training data.
Summary updated