# Subsampled Ensemble Can Improve Generalization Tail Exponentially

arXiv: https://arxiv.org/abs/2405.14741 · HTML: https://mlsanity.com/paper/2405.14741/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 33 of its 100 references that are in the map.
- First posted on arXiv 23 May 2024.

## Builds on (most cited first, 30 of 33)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015)
- [Learning to Optimize: A Primer and A Benchmark](https://mlsanity.com/paper/2103.12828/) (2021)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Reinforcement Learning for Integer Programming: Learning to Cut](https://mlsanity.com/paper/1906.04859/) (2019)
- [Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping](https://mlsanity.com/paper/2005.10785/) (2020)
- [High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails](https://mlsanity.com/paper/2106.14343/) (2021)
- [Loss minimization and parameter estimation with heavy tails](https://mlsanity.com/paper/1307.1827/) (2013)
- [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014)
- [Sub-Gaussian estimators of the mean of a random vector](https://mlsanity.com/paper/1702.00482/) (2017)
- [Learning to branch with Tree MDPs](https://mlsanity.com/paper/2205.11107/) (2022)
- [A Survey for Solving Mixed Integer Programming via Machine Learning](https://mlsanity.com/paper/2203.02878/) (2022)
- [Empirical risk minimization for heavy-tailed losses](https://mlsanity.com/paper/1406.2462/) (2014)
- [Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems](https://mlsanity.com/paper/2311.04161/) (2023)
- [Heavy-tailed Representations, Text Polarity Classification & Data Augmentation](https://mlsanity.com/paper/2003.11593/) (2020)
- [Machine Learning for Cutting Planes in Integer Programming: A Survey](https://mlsanity.com/paper/2302.09166/) (2023)
- [On Empirical Risk Minimization with Dependent and Heavy-Tailed Data](https://mlsanity.com/paper/2109.02224/) (2021)
- [Learning Primal Heuristics for Mixed Integer Programs](https://mlsanity.com/paper/2107.00866/) (2021)
- [Learning without Concentration for General Loss Functions](https://mlsanity.com/paper/1410.3192/) (2014)
- [Online Bootstrap Inference with Nonconvex Stochastic Gradient Descent Estimator](https://mlsanity.com/paper/2306.02205/) (2023)
- [Boosting Random Forests to Reduce Bias; One-Step Boosted Forest and its Variance Estimate](https://mlsanity.com/paper/1803.08000/) (2018)
- [Error Estimation for Randomized Least-Squares Algorithms via the Bootstrap](https://mlsanity.com/paper/1803.08021/) (2018)
- [Minimal Variance Sampling in Stochastic Gradient Boosting](https://mlsanity.com/paper/1910.13204/) (2019)
- [Sample average approximation with heavier tails I: non-asymptotic bounds with weak assumptions and stochastic constraints](https://mlsanity.com/paper/1705.00822/) (2017)
- [When can we improve on sample average approximation for stochastic optimization?](https://mlsanity.com/paper/1907.08334/) (2019)
- [Fast learning rates with heavy-tailed losses](https://mlsanity.com/paper/1609.09481/) (2016)

## Abstract (arXiv)

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.