Skip to Main content Skip to Navigation
Conference papers

Fast boosting using adversarial bandits

R. Busa-Fekete 1 Balázs Kégl 1, 2, 3
2 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
Abstract : In this paper we apply multi-armed bandits (MABs) to improve the computational complexity of AdaBoost. AdaBoost constructs a strong classifier in a stepwise fashion by selecting simple base classifiers and using their weighted ''vote'' to determine the final classification. We model this stepwise base classifier selection as a sequential decision problem, and optimize it with MABs where each arm represents a subset of the base classifier set. The MAB gradually learns the ''usefulness'' of the subsets, and selects one of the subsets in each iteration. AdaBoost then searches only this subset instead of optimizing the base classifier over the whole space. The main improvement of this paper over a previous approach is that we use an adversarial bandit algorithm instead of stochastic bandits. This choice allows us to prove a weak-to-strong-learning theorem, which means that the proposed technique remains a boosting algorithm in a formal sense. We demonstrate on benchmark datasets that our technique can achieve a generalization performance similar to standard AdaBoost for a computational cost that is an order of magnitude smaller.
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Sabine Starita Connect in order to contact the contributor
Submitted on : Friday, August 12, 2011 - 12:30:38 PM
Last modification on : Thursday, July 8, 2021 - 3:47:51 AM
Long-term archiving on: : Sunday, November 13, 2011 - 2:21:13 AM


Files produced by the author(s)


  • HAL Id : in2p3-00614564, version 1



R. Busa-Fekete, Balázs Kégl. Fast boosting using adversarial bandits. 27th International Conference on Machine Learning (ICML 2010), Jun 2010, Haifa, Israel. pp.143-150. ⟨in2p3-00614564⟩



Les métriques sont temporairement indisponibles