Research map / Learning theory and algorithms / Kernels and regression theory
Subsampled Ensemble Can Improve Generalization Tail Exponentially
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MoVE and ROVE ensembling that output the most frequently retrieved (or most often epsilon-optimal) model from a base learner run on random subsamples, converting polynomial excess-risk tails into exponentially decaying ones.
Problem
Excess-risk tails of data-driven learning and stochastic optimization decay only polynomially under heavy-tailed data or slow base-learner rates; ensembling is usually justified by variance reduction, which gives only constant-factor gains.
Approach
Instead of averaging subsampled models, select the mode of the base learner's output distribution over subsamples (majority vote over models for discrete spaces; epsilon-optimality vote among retrieved models for continuous spaces), which turns the tail into an exponential bound in n/k.
Key results
- On heavy-tailed synthetic regression, ROVE and ROVEs substantially outperform the base MLP in expected MSE and tail probabilities across sample sizes.
- ROVE outperforms bagging when noise tails are heavier (Pareto shape 1.1), while bagging wins for shape 2.1.
- Across stochastic programs, ROVE and ROVEs beat the SAA base in most cases; MoVE degrades when optima are multiple, while ROVE stays strong.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ROVE or ROVEs instead of the base learner | MLP regression with Pareto noise · Synthetic regression, heavy-tailed noise | expected out-of-sample MSE | Helped |
| Use ROVE or ROVEs instead of the base learner | MLP regression with Pareto noise · Synthetic regression, heavy-tailed noise | tail probability of out-of-sample costs | Helped |
| Use ROVE or ROVEs instead of the base learner | MLP regression with Gaussian noise, H=4 · Synthetic regression, light-tailed noise | expected out-of-sample MSE | No clear effect |
| Use ROVE or ROVEs instead of the base learner | MLP regression with Gaussian noise · Synthetic regression, light-tailed noise | tail probability of out-of-sample costs | Helped |
| Use ROVE or ROVEs instead of bagging | MLP regression, H=4 · Synthetic regression, Pareto shape 1.1 | out-of-sample performance | Helped |
| Use ROVE or ROVEs instead of bagging | MLP regression, H=4 · Synthetic regression, Pareto shape 2.1 | test performance | Hurt |
| Use ROVE or ROVEs instead of the base learner | Decision tree regression · Synthetic regression, heavy-tailed noise | tail probability of out-of-sample costs | Helped |
| Use ROVE or ROVEs instead of RF, GBDT, or XGBoost | Decision tree regression · Synthetic regression, Pareto shape 1.5 | high-end tail performance | Helped |
| Use ROVE or ROVEs instead of RF, GBDT, or XGBoost | Decision tree regression · Synthetic regression, less heavy-tailed noise | out-of-sample performance | Mixed |
| Use ROVE instead of the base learner | MLP regression · UCI real datasets | tail probability of out-of-sample costs | Mixed |
| Use ROVEs instead of the base learner | MLP regression · UCI real datasets | tail probability of out-of-sample costs | Hurt |
| Use ROVE or ROVEs instead of the base learner | SAA stochastic-programming learner · Stochastic programs, excluding linear program | expected out-of-sample cost | Helped |
Surprising findings
- On real datasets, ROVEs (with data splitting) underperforms the base learner.
- MoVE performs slightly worse than the base SAA under small sample sizes on the linear program.
Limitations
- Subsampling increases model bias, so the method suits low-bias, expressive base learners.
- Tail guarantee requires the mode of the base learner's sampling distribution to be a reasonably good model.
- ROVEs data splitting halves the data and underperforms on real datasets.
Experimental setup
Datasets: Bike Sharing Superconductivity Gas Turbine Emission synthetic Pareto/Gaussian-noise regression data stochastic program instances (resource allocation, supply chain network design, maximum weight matching, linear program,
Benchmarks: Bike Sharing Superconductivity Gas Turbine Emission synthetic Pareto/Gaussian regression stochastic programs (resource allocation, network design, matching, LP, portfolio)
Metrics: expected out-of-sample cost (MSE) tail probability of out-of-sample cost running time
Baselines: base learner (single MLP / decision tree / SAA) bagging (subagging) Random Forests GBDT XGBoost
Builds on: bagging subagging sample average approximation U-statistics concentration median-of-means
Closest papers by meaning
- Rethinking LLM Ensembling from the Perspective of Mixture Models (ICML 2026 · similarity 0.86)
- Theoretical Limitations of Ensembles in the Age of Overparameterization (ICML 2025 · similarity 0.85)
- Understanding Overadaptation in Supervised Fine-Tuning: The Role of Ensemble Methods (ICML 2025 · similarity 0.84)
- Ex Uno Pluria: Insights on Ensembling in Low Precision Number Systems (NeurIPS 2024 · similarity 0.84)
- No Free Lunch from Random Feature Ensembles: Scaling Laws and Near-Optimality Conditions (ICML 2025 · similarity 0.84)
- Free Lunch in the Forest: Functionally-Identical Pruning of Boosted Tree Ensembles (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.