  We introduce and study several measures of complexity of functions from the
convex hull of a given base class. These complexity measures take into account
the sparsity of the weights of a convex combination as well as certain
clustering properties of the base functions involved in it. We prove new upper
confidence bounds on the generalization error of ensemble (voting)
classification algorithms that utilize the new complexity measures along with
the empirical distributions of classification margins, providing a better
explanation of generalization performance of large margin classification
methods.
