Training-Time Optimization of a Budgeted Booster

We consider the problem of feature efficient prediction – a setting where features have costs, and the learner is limited by a budget constraint on the total cost of the features it can examine in test time. We focus on solv-ing this problem with boosting by optimiz-ing the choice of base learners in the train-ing phase and stopping the boosting process when the learner’s budget runs out. We ex-perimentally show that in the case of random costs, our method improves upon a previous approach of Reyzin [9] of drawing as many random samples as the budget allows from a trained AdaBoost ensemble. We also experi-mentally show that our method also outper-forms pruned decision trees, a natural bud-geted classifier.