On the dynamics of boosting

Cynthia Rudin, Ingrid Daubechies, Robert E. Schapire

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

5 Scopus citations


In order to understand AdaBoost's dynamics, especially its ability to maximize margins, we derive an associated simplified nonlinear iterated map and analyze its behavior in low-dimensional cases. We find stable cycles for these cases, which can explicitly be used to solve for Ada- Boost's output. By considering AdaBoost as a dynamical system, we are able to prove R̈atsch and Warmuth's conjecture that AdaBoost may fail to converge to a maximal-margin combined classifier when given a 'nonoptimal' weak learning algorithm. AdaBoost is known to be a coordinate descent method, but other known algorithms that explicitly aim to maximize the margin (such as AdaBoost and arc-gv) are not. We consider a differentiable function for which coordinate ascent will yield a maximum margin solution. We then make a simple approximation to derive a new boosting algorithm whose updates are slightly more aggressive than those of arcgv.

Original languageEnglish (US)
Title of host publicationAdvances in Neural Information Processing Systems 16 - Proceedings of the 2003 Conference, NIPS 2003
PublisherNeural information processing systems foundation
ISBN (Print)0262201526, 9780262201520
StatePublished - 2004
Externally publishedYes
Event17th Annual Conference on Neural Information Processing Systems, NIPS 2003 - Vancouver, BC, Canada
Duration: Dec 8 2003Dec 13 2003

Publication series

NameAdvances in Neural Information Processing Systems
ISSN (Print)1049-5258


Other17th Annual Conference on Neural Information Processing Systems, NIPS 2003
CityVancouver, BC

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing


Dive into the research topics of 'On the dynamics of boosting'. Together they form a unique fingerprint.

Cite this