Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper establishes a tight generalization bound for AdaBoost, showing that its generalization error can be expressed as \(Θ\left(\frac{d\ln(nγ^{2}/d)}{nγ^2}+\frac{\ln(1/δ)}{n}\right)\), where \(γ\) represents the weak learner's advantage, \(d\) is the VC-dimension, \(n\) is the sample size, and \(δ\) is the confidence parameter. The significance of this result lies in providing a clear upper bound that complements existing lower bounds from prior research, enhancing our understanding of AdaBoost's performance. The proof leverages the relationship between AdaBoost's voting classifier and a newly introduced margin-based generalization bound for voting classifiers, contributing to the theoretical foundations of ensemble methods in machine learning.
AdaBoost's generalization error can be tightly bounded, revealing critical insights into its performance under varying conditions.
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.