# Tight Generalization Bound for AdaBoost

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 49 references that are in the map.
- First posted on arXiv 29 Jul 2026.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [TabArena: A Living Benchmark for Machine Learning on Tabular Data](https://mlsanity.com/paper/2506.16791/) (2025)
- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [Efficient, Noise-Tolerant, and Private Learning via Boosting](https://mlsanity.com/paper/2002.01100/) (2020)
- [Online Agnostic Boosting via Regret Minimization](https://mlsanity.com/paper/2003.01150/) (2020)
- [Multiclass Boosting: Simple and Intuitive Weak Learning Criteria](https://mlsanity.com/paper/2307.00642/) (2023)
- [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)
- [Improved Margin Generalization Bounds for Voting Classifiers](https://mlsanity.com/paper/2502.16462/) (2025)
- [Boosting, Voting Classifiers and Randomized Sample Compression Schemes](https://mlsanity.com/paper/2402.02976/) (2024)
- [The Cost of Parallelizing Boosting](https://mlsanity.com/paper/2402.15145/) (2024)
- [Sample-Efficient Agnostic Boosting](https://mlsanity.com/paper/2410.23632/) (2024)
- [Sample-Optimal Agnostic Boosting with Unlabeled Data](https://mlsanity.com/paper/2503.04706/) (2025)
- [Optimal Parallelization of Boosting](https://mlsanity.com/paper/2408.16653/) (2024)
- [Of Dice and Games: A Theory of Generalized Boosting](https://mlsanity.com/paper/2412.08012/) (2024)
- [Improved Replicable Boosting with Majority-of-Majorities](https://mlsanity.com/paper/2501.18388/) (2025)
- [Revisiting Agnostic Boosting](https://mlsanity.com/paper/2503.09384/) (2025)
- [Tight Margin-Based Generalization Bounds for Voting Classifiers over Finite Hypothesis Sets](https://mlsanity.com/paper/2511.20407/) (2025)
- [Sample-Near-Optimal Agnostic Boosting with Improved Running Time](https://mlsanity.com/paper/2601.11265/) (2026)

## Abstract (arXiv)

In this paper we show that the generalization error of AdaBoost is Thetabig(tfracdln(nγ2/d)nγ2+tfracln(1/δ)nbig), where γ is the advantage guaranteed by the weak learner, d is the VC-dimension of the class containing the weak hypotheses, n is the sample size, and δ is the confidence parameter. The contribution of this paper is the upper bound; the matching lower bound follows from prior work. The upper bound proof follows by combining the known fact that AdaBoost outputs a voting classifier whose voting function has zero empirical γ/2-margin loss with what is, to the best of our knowledge, a new margin-based generalization bound for voting classifiers.