Carnegie Mellon University
SpeedBoost: Anytime Prediction with Uniform Near-Optimality

Alexander Grubb and J. Andrew (Drew) Bagnell
Fifteenth International Conference on Artificial Intelligence and Statistics, May, 2012.

  • Adobe portable document format (pdf) (2MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

We present SpeedBoost, a natural extension of functional gradient descent, for learning anytime predictors, which automatically trade computation time for predictive accuracy by selecting from a set of simpler candidate predictors. These anytime predictors not only generate approximate predictions rapidly, but are capable of using extra resources at prediction time, when available, to improve performance. We also demonstrate how our framework can be used to select weak predictors which target certain subsets of the data, allowing for efficient use of computational resources on difficult examples. We also show that variants of the SpeedBoost algorithm produce predictors which are provably competitive with any possible sequence of weak predictors with the same total complexity.

Boosting, Anytime Prediction, Machine Learning, Functional Gradient Methods

Sponsor: U.S. Army Research Laboratory, Collaborative Technology Alliance Program

Text Reference
Alexander Grubb and J. Andrew (Drew) Bagnell, "SpeedBoost: Anytime Prediction with Uniform Near-Optimality," Fifteenth International Conference on Artificial Intelligence and Statistics, May, 2012.

BibTeX Reference
   author = "Alexander Grubb and J. Andrew (Drew) Bagnell",
   title = "SpeedBoost: Anytime Prediction with Uniform Near-Optimality",
   booktitle = "Fifteenth International Conference on Artificial Intelligence and Statistics",
   month = "May",
   year = "2012",