Tight Generalization Bound for AdaBoost

arXiv:2607.26838v1 Announce Type: new Abstract: In this paper we show that the generalization error of AdaBoost is Thetaig(frac{dln(ngamma^{2}/d)}{ngamma^2}+frac{ln(1/elta)}{n}ig), where gamma 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 elta 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 gamma/2-margin loss with what is, to the best of our knowledge, a new margin-based generalization bound for voting classifiers.

Source: arXiv cs.LG | 2026-07-30