Dynamics of AdaBoost

Abstract

AdaBoost (Freund and Schapire 97) is one of the most successful and popular machine learning algorithms, though some of its basic convergence properties were not understood until recently. I will discuss the recent results on AdaBoost's convergence, which were obtained by analyzing an iterated map that is derived from the algorithm. This map exhibits cyclic behavior that can be understood analytically. This approach allows us to solve a well-studied problem of machine learning, namely whether AdaBoost achieves a "maximum margin" solution.