# Margin-Based Generalization Lower Bounds for Boosted Classifiers

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Sep 2019.

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

- [Optimal Weak to Strong Learning](https://mlsanity.com/paper/2206.01563/) (2022)
- [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)
- [Improved Margin Generalization Bounds for Voting Classifiers](https://mlsanity.com/paper/2502.16462/) (2025)
- [Sample Selection via Contrastive Fragmentation for Noisy Label Regression](https://mlsanity.com/paper/2502.17771/) (2025)
- [Boosting, Voting Classifiers and Randomized Sample Compression Schemes](https://mlsanity.com/paper/2402.02976/) (2024)
- [Tight Margin-Based Generalization Bounds for Voting Classifiers over Finite Hypothesis Sets](https://mlsanity.com/paper/2511.20407/) (2025)
- [Scalable Optimal Margin Distribution Machine](https://mlsanity.com/paper/2305.04837/) (2023)
- [Tight Generalization Bound for AdaBoost](https://mlsanity.com/paper/2607.26838/) (2026)

## Abstract (arXiv)

Boosting is one of the most successful ideas in machine learning. The most well-accepted explanations for the low generalization error of boosting algorithms such as AdaBoost stem from margin theory. The study of margins in the context of boosting algorithms was initiated by Schapire, Freund, Bartlett and Lee (1998) and has inspired numerous boosting algorithms and generalization bounds. To date, the strongest known generalization (upper bound) is the kth margin bound of Gao and Zhou (2013). Despite the numerous generalization upper bounds that have been proved over the last two decades, nothing is known about the tightness of these bounds. In this paper, we give the first margin-based lower bounds on the generalization error of boosted classifiers. Our lower bounds nearly match the kth margin bound and thus almost settle the generalization performance of boosted classifiers in terms of margins.