Z. Barutcuoglu, P. M. Long and R. A. Servedio. One-pass boosting. NIPS*07. (Paper available in postscript and PDF.)

---

Abstract
This paper studies boosting algorithms that make a single pass over a set of base classifiers: rather than choosing the "best" base classifier in each round, they pick a random order over the base classifiers, and use the tth base classifier during the tth round of boosting. We first analyze a one-pass algorithm in the setting of boosting with diverse base classifiers. Our guarantee is the same as the best proved for any boosting algorithm, but our one-pass algorithm is much faster than previous approaches. We next exhibit a random source of examples for which a ``picky'' variant of AdaBoost that skips poor base classifiers can outperform the standard AdaBoost algorithm, which uses every base classifier, by an exponential factor. Experiments with Reuters and synthetic data show that one-pass boosting can substantially improve on the accuracy of Naive Bayes, and that picky boosting can sometimes lead to a further improvement in accuracy.