On the Doubt about Margin Explanation of Boosting

Margin theory provides one of the most popular explanations to the success of $\mathtt{\text{AdaBoost}}$, where the central point lies in the recognition that $\mathit{\text{margin}}$ is the key for characterizing the performance of $\mathtt{\text{AdaBoost}}$. This theory has been very influential, e.g., it has been used to argue that $\mathtt{\text{AdaBoost}}$ usually does not overfit since it tends to enlarge the margin even after the training error reaches zero. Previously the $\mathit{\text{minimum}}\mathit{\text{margin}}\mathit{\text{bound}}$ was established for $\mathtt{\text{AdaBoost}}$, however, \cite{Breiman1999} pointed out that maximizing the minimum margin does not necessarily lead to a better generalization. Later, \cite{Reyzin:Schapire2006} emphasized that the margin distribution rather than minimum margin is crucial to the performance of $\mathtt{\text{AdaBoost}}$. In this paper, we first present the $k\mathit{\text{th}}\mathit{\text{margin}}\mathit{\text{bound}}$ and further study on its relationship to previous work such as the minimum margin bound and Emargin bound. Then, we improve the previous empirical Bernstein bounds \citep{Maurer:Pontil2009,Audibert:Munos:Szepesvari2009}, and based on such findings, we defend the margin-based explanation against Breiman’s doubts by proving a new generalization error bound that considers exactly the same factors as \cite{Schapire:Freund:Bartlett:Lee1998} but is sharper than \cite{Breiman1999}'s minimum margin bound. By incorporating factors such as average margin and variance, we present a generalization error bound that is heavily related to the whole margin distribution. We also provide margin distribution bounds for generalization error of voting classifiers in finite VC-dimension space.