Abstract
Bagging is a popular ensemble technique to improve the accuracy of machine learning models. It hinges on the well-established rationale that, by repeatedly retraining on resampled data, the aggregated model exhibits lower variance and hence higher stability, especially for discontinuous base learners. In this paper, we provide a new perspective on bagging: By suitably aggregating the base learners at the parametrization instead of the output level, bagging improves generalization performances exponentially, a strength that is significantly more powerful than variance reduction. More precisely, we show that for general stochastic optimization problems that suffer from slowly (i.e., polynomially) decaying generalization errors, bagging can effectively reduce these errors to an exponential decay. Moreover, this power of bagging is agnostic to the solution schemes, including common empirical risk minimization, distributionally robust optimization, and various regularizations. We demonstrate how bagging can substantially improve generalization performances in a range of examples involving heavy-tailed data that suffer from intrinsically slow rates.
Introduction
In machine learning and stochastic optimization, a critical metric is "excess risk"—the performance gap between a trained model and the theoretical optimum. For many problems, particularly those involving heavy-tailed data common in financial markets or large-scale language model datasets, the probability of a model performing poorly decays slowly as more data is added, following a "polynomial tail."
Traditional ensemble methods like bagging (Bootstrap Aggregating) are typically justified by their ability to reduce variance or improve stability. However, variance reduction generally only offers a constant-factor improvement and does not alter the fundamental rate at which a model's risk converges. This research demonstrates that by shifting the focus of aggregation from model outputs to the model parameters themselves, bagging can fundamentally accelerate this convergence rate from polynomial to exponential.
Methodology: Model-Level Aggregation
The core innovation presented is model-level aggregation, which aims to estimate the mode of the model distribution rather than the mean of its predictions. Two primary algorithms are introduced:
- MoVE (Majority Vote Ensembling): Designed for discrete decision spaces. It runs the base learner on multiple random subsamples and selects the specific model that appears most frequently.
- ROVE (Retrieval and $\epsilon$-Optimality Vote Ensembling): Tailored for continuous spaces where exact model matches are rare. ROVE uses a two-phase approach: first, collecting a pool of candidate models from subsamples, and second, evaluating these candidates on new subsamples to select the one most likely to be "$\epsilon$-optimal" (within a small margin of the best performer).
Unlike standard bagging, which averages predictions and can be skewed by outliers, these methods identify the most "typical" high-performing model, providing significant robustness to extreme data points.
Experimental Results
The researchers validated these approaches across synthetic data with Pareto and Gaussian noise, real-world UCI datasets (e.g., Bike Sharing, Wine Quality), and classic stochastic programming problems.
Key findings include:
- Exponential Tail Improvement: In environments with heavy-tailed noise (e.g., Pareto shape = 1.1), ROVE and MoVE significantly outperformed both the base learner and standard bagging. The "tail probability"—the likelihood of a very poor result—was reduced by orders of magnitude, transforming polynomial decay into exponential decay.
- The Power of the Mode: Traditional bagging's reliance on mean estimation makes it vulnerable to heavy-tailed noise. By seeking the mode, MoVE and ROVE effectively filter out "noisy" models produced by outlier-heavy subsamples.
- Scalability and Efficiency: As neural network complexity increases, the benefits of ROVE become more pronounced. Furthermore, because subsampled optimizations are smaller and parallelizable, this ensemble approach can be computationally competitive with training a single large model on the full dataset.
Discussion and Conclusion
While highly effective, these methods involve a trade-off: reducing subsample size ($k$) to thin the tails can increase the bias of individual base learners. The exponential boost also requires the base learner to have a minimum level of predictive power. Future research may explore integrating these voting mechanisms directly into deep learning training loops rather than using them as post-hoc wrappers.
In summary, this work reveals that bagging's true power lies not just in variance reduction, but in its ability to fundamentally change the generalization behavior of models in noisy, heavy-tailed environments.
Summary updated