Accelerating AdaBoost using UCB

Róbert Busa-Fekete, Balázs KéglKDD 2009 · OpenReview

Abstract

This paper explores how multi-armed bandits (MABs) can be applied to accelerate AdaBoost. AdaBoost constructs a strong classifier in a stepwise fashion by adding simple base classifiers to a pool. However, searching through all features in each iteration becomes computationally expensive in high-dimensional settings. We introduce a method that intelligently selects subsets of features using the Upper Confidence Bound (UCB) algorithm, significantly reducing training time while maintaining competitive accuracy.

Introduction

AdaBoost is a cornerstone of ensemble learning, yet its scalability is limited by the feature search process. In each boosting iteration, the algorithm typically evaluates all $d$ features to find the optimal split for a base classifier. For modern datasets with tens of thousands of features, this $O(d)$ complexity per step makes training prohibitively slow. While random feature subsampling (e.g., LazyBoost) offers speedups, it lacks a mechanism to prioritize features that are consistently informative.

Methodology: UCB-Boost

The proposed approach models feature selection as a Multi-Armed Bandit (MAB) problem. The feature space is partitioned into several subsets, or "arms." In each iteration, instead of an exhaustive search, the algorithm employs the Upper Confidence Bound (UCB) strategy to select the most promising subsets.

UCB balances two critical factors:

  1. Exploitation: Selecting subsets that have yielded high-performing base learners in previous steps.
  2. Exploration: Investigating less-frequently used subsets to account for shifts in data weights as boosting progresses.

The "reward" for an arm is derived from the "edge" $\gamma$ of the best base classifier found within that subset, mapped to a $[0, 1]$ range. By evaluating only the top $k$ arms (the $UCB(k)$ variant), the search space is drastically pruned.

Experimental Evaluation

The method was tested on the KDD Cup 2009 datasets, which include both "Small" (230 features) and "Large" (15,000 features) versions across three tasks: Churn, Appetency, and Up-selling. Initial feature selection via information gain was used to reduce the initial pool before applying UCB-Boost.

Results and Discussion

The UCB-accelerated AdaBoost demonstrated robust convergence across various base learners, including decision stumps, products of base learners, and decision trees. On the high-dimensional "Large" dataset, the algorithm successfully completed 8,000 iterations in under 10 hours, a significant improvement over standard exhaustive search.

Performance of different base learners (Stumps, Products, Trees) over 10,000 iterations on the validation set.

As shown in the convergence plots, the performance stabilizes as the number of iterations increases, indicating that the UCB strategy effectively identifies useful features even as the instance weights change. The final performance on the KDD Cup tasks was highly competitive, particularly in the "Up-selling" task where the method achieved an AUC within 1% of the challenge's winning entry.

Official validation and evaluation results from the KDD Cup challenge.

Conclusion

By framing feature selection as a bandit problem, we can significantly accelerate AdaBoost without sacrificing predictive power. The UCB strategy ensures that the algorithm remains focused on high-utility features while maintaining enough diversity to generalize well. Future work includes exploring feature dependencies within complex base learners and optimizing the partitioning of the feature space.

Summary updated

Abstract

This paper explores how multi-armed bandits (MABs) can be applied to accelerate AdaBoost. AdaBoost constructs a strong classifier in a stepwise fashion by adding simple base classifiers to a pool a...
BibTeX
@inproceedings{busafekete2009accelerating,
  author = {Róbert Busa-Fekete and Balázs Kégl},
  title = {{Accelerating AdaBoost using UCB}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2009},
  url = {https://openreview.net/forum?id=GlHERXrQTo1},
}
Figure