Complexities of convex combinations and bounding the generalization error in classification

2004/05/31 by Vladimir Koltchinskii, Dmitry Panchenko
Computer Science · Engineering · Mathematics · #Machine Learning and Algorithms #Machine Learning and ELM #Sparse and Compressive Sensing Techniques #math.PR #msc:60F15 #msc:62G05 #msc:62G20

paper · pdf · doi:10.1214/009053605000000228

published as Annals of Statistics 2005, Vol. 33, No. 4, 1455-1496 · 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)

openalex publication_date 2005/08/01 · arxiv created 2005/08/25 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• Some Local Measures of Complexity of Convex Hulls and Generalization Bounds
• Greedy Convex Ensemble
• Tight Margin-Based Generalization Bounds for Voting Classifiers over Finite Hypothesis Sets
• On the Current State of Research in Explaining Ensemble Performance Using Margins
• Empirical margin distributions and bounding the generalization error of combined classifiers