# Boosting, Voting Classifiers and Randomized Sample Compression Schemes

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 27 references that are in the map.
- First posted on arXiv 5 Feb 2024.

## Builds on (most cited first, 9 of 9)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [Bagging is an Optimal PAC Learner](https://mlsanity.com/paper/2212.02264/) (2022)
- [Optimal Weak to Strong Learning](https://mlsanity.com/paper/2206.01563/) (2022)
- [Margins are Insufficient for Explaining Gradient Boosting](https://mlsanity.com/paper/2011.04998/) (2020)
- [Margin-Based Generalization Lower Bounds for Boosted Classifiers](https://mlsanity.com/paper/1909.12518/) (2019)
- [The Impossibility of Parallelizing Boosting](https://mlsanity.com/paper/2301.09627/) (2023)
- [AdaBoost is not an Optimal Weak to Strong Learner](https://mlsanity.com/paper/2301.11571/) (2023)

## Built on by (most cited first, 3 of 3)

- [Learning with Monotone Adversarial Corruptions](https://mlsanity.com/paper/2601.02193/) (2026)
- [Credit Attribution and Stable Compression](https://mlsanity.com/paper/2406.15916/) (2024)
- [Tight Generalization Bound for AdaBoost](https://mlsanity.com/paper/2607.26838/) (2026)

## Abstract (arXiv)

In boosting, we aim to leverage multiple weak learners to produce a strong learner. At the center of this paradigm lies the concept of building the strong learner as a voting classifier, which outputs a weighted majority vote of the weak learners. While many successful boosting algorithms, such as the iconic AdaBoost, produce voting classifiers, their theoretical performance has long remained sub-optimal: The best known bounds on the number of training examples necessary for a voting classifier to obtain a given accuracy has so far always contained at least two logarithmic factors above what is known to be achievable by general weak-to-strong learners. In this work, we break this barrier by proposing a randomized boosting algorithm that outputs voting classifiers whose generalization error contains a single logarithmic dependency on the sample size. We obtain this result by building a general framework that extends sample compression methods to support randomized learning algorithms based on sub-sampling.