ebd9629fc3ae5e9f6611e2ee05a31cef-Reviews.html

This is an interesting paper on budgeted structured prediction where the costs of computing features is substantial. A naive approach to reducing computation would be to add an L1-regularization term to the optimization and only compute the non-zero-weight features. However, the paper is motivated by the observation that for specific instances, some features may not be computationally worthwhile to compute. A controller is constructed using reinforcement learning techniques to sequentially choose the subset of features to evaluate for prediction within the allocated budget. This is an empirical papers as there is not much in the way of new theory (no theorems, etc.) presented to support the combination of techniques and detailed engineering employed to realize improved efficiency.