Complexities of convex combinations and bounding the generalization error in classification

Abstract

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.

Published at http://dx.doi.org/10.1214/009053605000000228 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (4)

• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• Local Rademacher complexities
• Boosting with early stopping: Convergence and consistency
• Complexity regularization via localized random penalties

Cited by in corpus (7)

• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• Boosting with early stopping: Convergence and consistency
• Analysis of boosting algorithms using the smooth margin function
• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-${\ell }_1$-Norm Interpolated Classifiers
• Machine Learning with Operational Costs
• Dropout Rademacher Complexity of Deep Neural Networks
• On the Doubt about Margin Explanation of Boosting