Tight Generalization Bound for AdaBoost

In this paper we show that the generalization error of AdaBoost is Θ\big(\tfrac{d\ln(nγ^{2}/d)}{nγ^2}+\tfrac{\ln(1/δ)}{n}\big), 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.