mlsanityData to 14 Oct 2026

Tight Generalization Bound for AdaBoost

arXiv 2607.26838 ↗First posted 29 Jul 2026cs.LGcited by 0

Not on the map. Why?

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.

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

21 of 49 references.

References · 21

  1. 2016XGBoost: A Scalable Tree Boosting Systemcited by 5,166
  2. 2025TabArena: A Living Benchmark for Machine Learning on Tabular Datacited by 176
  3. 2022Reproducibility in Learningcited by 44
  4. 2020Efficient, Noise-Tolerant, and Private Learning via Boostingcited by 15
  5. 2020Online Agnostic Boosting via Regret Minimizationcited by 12
  6. 2023Multiclass Boosting: Simple and Intuitive Weak Learning Criteriacited by 11
  7. 2020Margins are Insufficient for Explaining Gradient Boostingcited by 10
  8. 2019Margin-Based Generalization Lower Bounds for Boosted Classifierscited by 9
  9. 2023The Impossibility of Parallelizing Boostingcited by 7
  10. 2023AdaBoost is not an Optimal Weak to Strong Learnercited by 6
  11. 2025Improved Margin Generalization Bounds for Voting Classifierscited by 4
  12. 2024Boosting, Voting Classifiers and Randomized Sample Compression Schemescited by 3
9 more
  1. 2024The Cost of Parallelizing Boostingcited by 3
  2. 2024Sample-Efficient Agnostic Boostingcited by 3
  3. 2025Sample-Optimal Agnostic Boosting with Unlabeled Datacited by 3
  4. 2024Optimal Parallelization of Boostingcited by 2
  5. 2024Of Dice and Games: A Theory of Generalized Boostingcited by 2
  6. 2025Improved Replicable Boosting with Majority-of-Majoritiescited by 2
  7. 2025Revisiting Agnostic Boostingcited by 2
  8. 2025Tight Margin-Based Generalization Bounds for Voting Classifiers over Finite Hypothesis Setscited by 2
  9. 2026Sample-Near-Optimal Agnostic Boosting with Improved Running Timecited by 1

Built on by

Not cited yet.