  Margin theory provides one of the most popular explanations to the success of
\texttt{AdaBoost}, where the central point lies in the recognition that
\textit{margin} is the key for characterizing the performance of
\texttt{AdaBoost}. This theory has been very influential, e.g., it has been
used to argue that \texttt{AdaBoost} usually does not overfit since it tends to
enlarge the margin even after the training error reaches zero. Previously the
\textit{minimum margin bound} was established for \texttt{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 \texttt{AdaBoost}. In this paper, we first present the
\textit{$k$th margin 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.
