Subsampled Ensemble Can Improve Generalization Tail Exponentially

Huajie Qian, Donghao Ying, Henry Lam, Wotao Yin

TL;DR

Ensemble learning is usually praised for reducing variance, but this paper reveals a much more powerful property: it can fundamentally transform the generalization error tail from a slow polynomial decay into a rapid exponential one. By using a novel "majority vote" at the model level rather than the prediction level, the authors demonstrate how to achieve order-of-magnitude improvements in stability and performance, particularly when dealing with heavy-tailed data common in finance, physics, and large language models.

What Problem Does This Paper Address?

In many real-world machine learning and optimization tasks, the data is "heavy-tailed"—meaning extreme outliers occur more frequently than a normal distribution would suggest. In these settings, standard learning algorithms like Sample Average Approximation (SAA) or Empirical Risk Minimization (ERM) suffer from slow generalization. Specifically, the probability of the model having a large "excess risk" (error beyond the theoretical optimum) decays only polynomially ($1/n^\alpha$).

While traditional ensemble methods like bagging are known to reduce variance, they typically only provide a constant-factor improvement in error. They don't change the underlying rate at which the tail of the error distribution vanishes. This paper aims to bridge that gap, providing a method to force that tail to decay exponentially, making the models significantly more robust to the "black swan" events inherent in heavy-tailed data.

Methods

The authors introduce two primary algorithms that perform voting at the model level rather than the prediction level:

  1. MoVE (Majority Vote Ensembling): Designed for discrete decision spaces. The algorithm repeatedly draws subsamples from the data, trains a base learner on each, and then outputs the model that appears most frequently (the mode).
  2. ROVE (Retrieval and $\epsilon$-Optimality Vote Ensembling): A generalization for continuous spaces where a simple majority vote would fail (since every trained model might be slightly different).
  3. Phase I (Retrieval): Train $B_1$ candidate models on different subsamples.
  4. Phase II (Voting): Evaluate these candidates on new subsamples. A candidate gets a "vote" if its performance is within $\epsilon$ of the best model on that specific subsample. The model with the most votes wins.

The core theoretical innovation is treating ensembling as a mode estimation problem. By maximizing the probability of selecting a "good" model, the authors transform a potentially heavy-tailed cost objective into a bounded probability objective (which always stays between 0 and 1). This bounded nature allows for much sharper concentration of measure, leading to the proven exponential tail decay.

Datasets

The researchers evaluated their methods across a diverse set of benchmarks:

  • Synthetic Data: Linear programs with polynomial tails, linear regression with heavy-tailed noise, and neural network regression tasks using Pareto-distributed noise.
  • Real-World Datasets (UCI Repository):
    • Bike Sharing: Predicting rental demand.
  • Superconductivity: Predicting critical temperatures.
  • Gas Turbine Emission: Predicting NOx emissions.
  • Additional sets: Wine Quality, Online News Popularity, and Appliances Energy.
  • Stochastic Programming Problems: Resource allocation, portfolio optimization, maximum weight matching, and supply chain network design.

Key Insights and Ideas

  • Mode vs. Mean: Traditional ensembling (like bagging) often averages predictions, which is akin to estimating a mean. If the underlying data is heavy-tailed, the mean is easily skewed by outliers. By instead estimating the mode of the model distribution, the ensemble focuses on the most frequently successful "type" of model, ignoring the erratic models produced by outlier-heavy subsamples.
  • Constant Inference Cost: Unlike standard bagging or random forests, where you must run all $B$ models at test time and aggregate their results, MoVE and ROVE output a single best model. This means the computational cost during deployment is identical to that of a single base learner.
  • Rate Improvement: The most striking finding is that ensembling isn't just a "tweak" for better accuracy; it's a fundamental change in the convergence rate of the error tail. This is a much stronger effect than the constant-factor gains seen in variance reduction.

Key Results

The authors prove that the excess risk tail of their ensemble methods decays as $C_2 \gamma^{n/k}$, where $n$ is the total data size and $k$ is the subsample size.

Empirically, the results are compelling:

  • Neural Networks: In heavy-tailed noise settings, ROVE significantly outperformed base learners and standard bagging in both expected cost and tail performance. Neural network results showing ROVE/ROVEs outperforming base learners in Pareto noise settings.

  • Comparison with Bagging: As the data tail becomes heavier (e.g., Pareto shape parameter moving from 2.1 to 1.1), ROVE's advantage over traditional bagging grows substantially. Comparison with bagging showing ROVE's superior tail performance as noise becomes heavier.

  • Stochastic Programs: Across various industrial optimization problems, the ensemble methods consistently delivered lower expected costs and tighter error bars than the base SAA algorithm. Results for stochastic programs showing significant cost reductions across multiple problem types.

Figure 1: Results of neural networks. (a)(b)(d)(e): Expected out-of-sample costs (MSE) with 95% confidence intervals under different noise distributions and varying numbers of hidden layers (H). (c) and (f): Tail probabilities of out-of-sample costs.
Comparison with bagging showing ROVE's superior tail performance as noise becomes heavier.
Results for stochastic programs showing significant cost reductions across multiple problem types.

Limitations and Future Work

  • Model Bias: Like all subsampling methods, using a subsample size $k$ that is too small can introduce model bias. The authors suggest a heuristic ($k = \max(10, n/200)$) but note that the optimal $k$ is problem-dependent.
  • Base Learner Requirement: The theory assumes the base learner has at least "reasonable" predictive power (i.e., the mode of its sampling distribution must be a good model). If the base learner is too weak, the ensemble cannot recover.
  • Hyperparameter Sensitivity: The $\epsilon$ threshold in ROVE is critical. While the authors propose an adaptive strategy to select $\epsilon$, further research into automated tuning for diverse model architectures would be beneficial.

Summary updated

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.
BibTeX
@inproceedings{qian2025subsampled,
  author = {Huajie Qian and Donghao Ying and Henry Lam and Wotao Yin},
  title = {{Subsampled Ensemble Can Improve Generalization Tail Exponentially}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=VJn4UKnEYS},
}
Figure