The dynamics of AdaBoost: Cyclic behavior and convergence of margins

Published

Journal Article

© 2004 Cynthia Rudin, Ingrid Daubechies and Robert E. Schapire. In order to study the convergence properties of the AdaBoost algorithm, we reduce AdaBoost to a nonlinear iterated map and study the evolution of its weight vectors. This dynamical systems approach allows us to understand AdaBoost's convergence properties completely in certain cases; for these cases we find stable cycles, allowing us to explicitly solve for AdaBoost's output. Using this unusual technique, we are able to show that AdaBoost does not always converge to a maximum margin combined classifier, answering an open question. In addition, we show that "nonoptimal" AdaBoost (where the weak learning algorithm does not necessarily choose the best weak classifier at each iteration) may fail to converge to a maximum margin classifier, even if "optimal" AdaBoost produces a maximum margin. Also, we show that if AdaBoost cycles, it cycles among "support vectors", i.e., examples that achieve the same smallest margin.

Duke Authors

Cited Authors

  • Rudin, C; Daubechies, I; Schapire, RE

Published Date

  • December 1, 2004

Published In

Volume / Issue

  • 5 /

Start / End Page

  • 1557 - 1595

Electronic International Standard Serial Number (EISSN)

  • 1533-7928

International Standard Serial Number (ISSN)

  • 1532-4435

Citation Source

  • Scopus