How boosting the margin can also boost classifier complexity

Lev Reyzin, Robert E. Schapire

Research output: Chapter in Book/Report/Conference proceedingConference contribution

93 Scopus citations


Boosting methods are known not to usually overfit training data even as the size of the generated classifiers becomes large. Schapire et al. attempted to explain this phenomenon in terms of the margins the classifier achieves on training examples. Later, however, Breiman cast serious doubt on this explanation by introducing a boosting algorithm, arc-gv, that can generate a higher margins distribution than AdaBoost and yet performs worse. In this paper, we take a close look at Breiman's compelling but puzzling results. Although we can reproduce his main finding, we find that the poorer performance of arc-gv can be explained by the increased complexity of the base classifiers it uses, an explanation supported by our experiments and entirely consistent with the margins theory. Thus, we find maximizing the margins is desirable, but not necessarily at the expense of other factors, especially base-classifier complexity.

Original languageEnglish (US)
Title of host publicationACM International Conference Proceeding Series - Proceedings of the 23rd International Conference on Machine Learning, ICML 2006
Number of pages8
StatePublished - 2006
Event23rd International Conference on Machine Learning, ICML 2006 - Pittsburgh, PA, United States
Duration: Jun 25 2006Jun 29 2006

Publication series

NameACM International Conference Proceeding Series


Other23rd International Conference on Machine Learning, ICML 2006
Country/TerritoryUnited States
CityPittsburgh, PA

All Science Journal Classification (ASJC) codes

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications


Dive into the research topics of 'How boosting the margin can also boost classifier complexity'. Together they form a unique fingerprint.

Cite this